Voir la source de Racine primitive modulo n

{{Titre mis en forme|Racine primitive modulo ''n''}}
{{Autre|les racines primitives complexes  de l'unité|Racine de l'unité}}

Les '''racines primitives modulo ''n'''''<ref>{{Dis.ar}}, {{§|54-57}}.</ref> sont un concept issu de l'[[arithmétique modulaire]], dans la [[théorie des nombres]]. Ce sont (lorsqu'il en existe) les [[Partie génératrice d'un groupe|générateurs]] du [[Groupe (mathématiques)|groupe]] des [[inversible]]s de l'[[Anneau ℤ/nℤ|anneau ℤ/''n''ℤ]].

== Définition ==
Si ''n'' est un [[Entier naturel|entier]] strictement positif, les nombres [[Premier avec|premiers avec]] ''n'', pris [[congruence sur les entiers|modulo]] ''n'', forment un groupe pour la multiplication, noté [[Anneau ℤ/nℤ#Groupe des unités|('''Z'''/''n'''''Z'''){{exp|×}}]] ou '''Z'''{{ind|''n''}}{{exp|×}}. Ce groupe est [[groupe cyclique|cyclique]] si et seulement si ''n'' est égal à 4 ou ''p''{{exp|''k''}} ou 2''p''{{exp|''k''}} pour un [[nombre premier]] ''p'' ≥ 3 et ''k'' ≥ 0<ref>Une démonstration est donnée dans l'article [[Anneau ℤ/nℤ#Groupe des unités|« Anneau '''Z'''/''n'''''Z''' », § « Groupe des unités »]].</ref>. Un générateur de ce groupe cyclique est appelé une racine primitive modulo ''n'', ou un élément primitif<ref>{{Ouvrage|langue=en|auteur1=D. Rasch|auteur2=J. Pilz|auteur3=R. Verdooren|auteur4=A. Gebhardt|titre=Optimal Experimental Design [[R (langage de programmation et environnement statistique)|with R]]|éditeur=[[Taylor & Francis]]|collection=[[Chapman & Hall]]/[[CRC Press]]|année=2011|passage=291|lire en ligne={{Google Livres|sgwKm8Ng_1cC|page=291}}}}.</ref> de '''Z'''{{ind|''n''}}{{exp|×}}. Une racine primitive modulo ''n'' est donc un entier ''g'' tel que tout inversible dans '''Z'''/''n'''''Z''' est une [[Puissance d'un nombre|puissance]] de ''g'' modulo ''n''.

== Exemples ==
Prenons par exemple ''n'' = 14. Les éléments de ('''Z'''/14'''Z'''){{exp|×}} sont les classes de congruence 1, 3, 5, 9, 11 et 13. Donc 3 est une racine primitive modulo 14, et l'on a 3{{2}} ≡ 9, 3{{3}} ≡ 13, 3{{4}} ≡ 11, 3{{5}} ≡ 5 et 3{{6}} ≡ 1 (modulo 14). La seule autre racine primitive modulo 14 est 5.

Voici une table contenant les plus petites racines primitives pour quelques valeurs de ''n'' ({{OEIS|id=A046145}}) :
{| class="wikitable centre" style="text-align:center"
|-
!scope="row"|''n''
|2||3||4||5||6||7||8||9||10||11||12||13||14
|-
!scope="row"|racine primitive mod ''n''
|1||2||3||2||5||3||-||2||3||2||-||2||3
|}

Voici une table donnant les plus petites racines primitives ''r'' modulo les nombres premiers ''p'' inférieurs à {{nombre|1000}} ({{OEIS|id=A001918}})<ref>[https://oeis.org/A001918/b001918.txt Table des racines primitives des {{formatnum:10000}} premiers nombres premiers].</ref> :

{| border=1 cellpadding=2
|----- align="center"
! ''p''
! ''r''
! ''p''
! ''r''
! ''p''
! ''r''
! ''p''
! ''r''
! ''p''
! ''r''
! ''p''
! ''r''
! ''p''
! ''r''
! ''p''
! ''r''
! ''p''
! ''r''
! ''p''
! ''r''
! ''p''
! ''r''
! ''p''
! ''r''
|----- align="center"
! [[2 (nombre)|2]] || bgcolor="lightgreen" | [[1 (nombre)|1]]
! [[47 (nombre)|47]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[109 (nombre)|109]] || bgcolor="lightgreen" | [[6 (nombre)|6]]
! [[191 (nombre)|191]] || bgcolor="lightgreen" | [[19 (nombre)|19]]
! [[269 (nombre)|269]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[353 (nombre)|353]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[439 (nombre)|439]] || bgcolor="lightgreen" | [[15 (nombre)|15]]
! [[523 (nombre)|523]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[617 (nombre)|617]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[709 (nombre)|709]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[811 (nombre)|811]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[907 (nombre)|907]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
|----- align="center"
! [[3 (nombre)|3]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[53 (nombre)|53]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[113 (nombre)|113]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[193 (nombre)|193]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[271 (nombre)|271]] || bgcolor="lightgreen" | [[6 (nombre)|6]]
! [[359 (nombre)|359]] || bgcolor="lightgreen" | [[7 (nombre)|7]]
! [[443 (nombre)|443]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[541 (nombre)|541]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[619 (nombre)|619]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[719 (nombre)|719]] || bgcolor="lightgreen" | [[11 (nombre)|11]]
! [[821 (nombre)|821]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[911 (nombre)|911]] || bgcolor="lightgreen" | [[17 (nombre)|17]]
|----- align="center"
! [[5 (nombre)|5]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[59 (nombre)|59]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[127 (nombre)|127]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[197 (nombre)|197]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[277 (nombre)|277]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[367 (nombre)|367]] || bgcolor="lightgreen" | [[6 (nombre)|6]]
! [[449 (nombre)|449]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[547 (nombre)|547]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[631 (nombre)|631]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[727 (nombre)|727]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[823 (nombre)|823]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[919 (nombre)|919]] || bgcolor="lightgreen" | [[7 (nombre)|7]]
|----- align="center"
! [[7 (nombre)|7]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[61 (nombre)|61]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[131 (nombre)|131]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[199 (nombre)|199]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[281 (nombre)|281]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[373 (nombre)|373]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[457 (nombre)|457]] || bgcolor="lightgreen" | [[13 (nombre)|13]]
! [[557 (nombre)|557]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[641 (nombre)|641]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[733 (nombre)|733]] || bgcolor="lightgreen" | [[6 (nombre)|6]]
! [[827 (nombre)|827]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[929 (nombre)|929]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
|----- align="center"
! [[11 (nombre)|11]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[67 (nombre)|67]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[137 (nombre)|137]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[211 (nombre)|211]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[283 (nombre)|283]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[379 (nombre)|379]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[461 (nombre)|461]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[563 (nombre)|563]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[643 (nombre)|643]] || bgcolor="lightgreen" | [[11 (nombre)|11]]
! [[739 (nombre)|739]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[829 (nombre)|829]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[937 (nombre)|937]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
|----- align="center"
! [[13 (nombre)|13]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[71 (nombre)|71]] || bgcolor="lightgreen" | [[7 (nombre)|7]]
! [[139 (nombre)|139]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[223 (nombre)|223]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[293 (nombre)|293]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[383 (nombre)|383]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[463 (nombre)|463]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[569 (nombre)|569]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[647 (nombre)|647]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[743 (nombre)|743]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[839 (nombre)|839]] || bgcolor="lightgreen" | [[11 (nombre)|11]]
! [[941 (nombre)|941]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
|----- align="center"
! [[17 (nombre)|17]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[73 (nombre)|73]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[149 (nombre)|149]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[227 (nombre)|227]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[307 (nombre)|307]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[389 (nombre)|389]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[467 (nombre)|467]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[571 (nombre)|571]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[653 (nombre)|653]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[751 (nombre)|751]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[853 (nombre)|853]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[947 (nombre)|947]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
|----- align="center"
! [[19 (nombre)|19]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[79 (nombre)|79]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[151 (nombre)|151]] || bgcolor="lightgreen" | [[6 (nombre)|6]]
! [[229 (nombre)|229]] || bgcolor="lightgreen" | [[6 (nombre)|6]]
! [[311 (nombre)|311]] || bgcolor="lightgreen" | [[17 (nombre)|17]]
! [[397 (nombre)|397]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[479 (nombre)|479]] || bgcolor="lightgreen" | [[13 (nombre)|13]]
! [[577 (nombre)|577]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[659 (nombre)|659]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[757 (nombre)|757]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[857 (nombre)|857]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[953 (nombre)|953]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
|----- align="center"
! [[23 (nombre)|23]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[83 (nombre)|83]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[157 (nombre)|157]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[233 (nombre)|233]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[313 (nombre)|313]] || bgcolor="lightgreen" | [[10 (nombre)|10]]
! [[401 (nombre)|401]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[487 (nombre)|487]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[587 (nombre)|587]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[661 (nombre)|661]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[761 (nombre)|761]] || bgcolor="lightgreen" | [[6 (nombre)|6]]
! [[859 (nombre)|859]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[967 (nombre)|967]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
|----- align="center"
! [[29 (nombre)|29]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[89 (nombre)|89]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[163 (nombre)|163]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[239 (nombre)|239]] || bgcolor="lightgreen" | [[7 (nombre)|7]]
! [[317 (nombre)|317]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[409 (nombre)|409]] || bgcolor="lightgreen" | [[21 (nombre)|21]]
! [[491 (nombre)|491]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[593 (nombre)|593]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[673 (nombre)|673]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[769 (nombre)|769]] || bgcolor="lightgreen" | [[11 (nombre)|11]]
! [[863 (nombre)|863]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[971 (nombre)|971]] || bgcolor="lightgreen" | [[6 (nombre)|6]]
|----- align="center"
! [[31 (nombre)|31]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[97 (nombre)|97]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[167 (nombre)|167]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[241 (nombre)|241]] || bgcolor="lightgreen" | [[7 (nombre)|7]]
! [[331 (nombre)|331]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[419 (nombre)|419]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[499 (nombre)|499]] || bgcolor="lightgreen" | [[7 (nombre)|7]]
! [[599 (nombre)|599]] || bgcolor="lightgreen" | [[7 (nombre)|7]]
! [[677 (nombre)|677]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[773 (nombre)|773]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[877 (nombre)|877]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[977 (nombre)|977]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
|----- align="center"
! [[37 (nombre)|37]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[101 (nombre)|101]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[173 (nombre)|173]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[251 (nombre)|251]] || bgcolor="lightgreen" | [[6 (nombre)|6]]
! [[337 (nombre)|337]] || bgcolor="lightgreen" | [[10 (nombre)|10]]
! [[421 (nombre)|421]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[503 (nombre)|503]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[601 (nombre)|601]] || bgcolor="lightgreen" | [[7 (nombre)|7]]
! [[683 (nombre)|683]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[787 (nombre)|787]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[881 (nombre)|881]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[983 (nombre)|983]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
|----- align="center"
! [[41 (nombre)|41]] || bgcolor="lightgreen" | [[6 (nombre)|6]]
! [[103 (nombre)|103]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[179 (nombre)|179]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[257 (nombre)|257]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[347 (nombre)|347]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[431 (nombre)|431]] || bgcolor="lightgreen" | [[7 (nombre)|7]]
! [[509 (nombre)|509]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[607 (nombre)|607]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[691 (nombre)|691]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[797 (nombre)|797]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[883 (nombre)|883]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[991 (nombre)|991]] || bgcolor="lightgreen" | [[6 (nombre)|6]]
|----- align="center"
! [[43 (nombre)|43]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[107 (nombre)|107]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[181 (nombre)|181]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[263 (nombre)|263]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[349 (nombre)|349]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[433 (nombre)|433]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[521 (nombre)|521]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[613 (nombre)|613]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[701 (nombre)|701]] || bgcolor="lightgreen" | [[2 (nombre)|2]]
! [[809 (nombre)|809]] || bgcolor="lightgreen" | [[3 (nombre)|3]]
! [[887 (nombre)|887]] || bgcolor="lightgreen" | [[5 (nombre)|5]]
! [[997 (nombre)|997]] || bgcolor="lightgreen" | [[7 (nombre)|7]]
|----- align="center"
|}

== Calcul ==
On ne connaît aucune formule générale simple pour calculer les racines primitives modulo ''n''. Il existe cependant une méthode pour tester si un entier ''m'' est racine primitive mod ''n'' — c'est-à-dire si son [[ordre multiplicatif]] modulo ''n'' est égal à [[indicatrice d'Euler|φ(''n'')]] (l'[[Ordre (théorie des groupes)|ordre]] de '''Z'''{{ind|n}}{{exp|×}}) — qui est plus rapide qu'un simple calcul mod ''n'' de toutes ses puissances successives jusqu'à l'exposant φ(''n'') :

<!-- Je pense qu'il faut qu'aucun diviseur premier de 'n' ne divise 'm'. et que si un diviseur premier de 'phi(n)' divise 'n' on l'ignore. (par exemple dans le tableau on voit que 3 est racine primitive de 79, seulement phi(79) = 78 = 0 mod 3, donc incohérent avec le fait qu'aucun diviseur premier de phi(n) ne doit diviser m, comme l'explique la méthode du paragraphe). -->
{{Retrait|On a au préalable calculé φ(''n'') et déterminé ses [[diviseur]]s premiers, soit ''p''{{ind|1}},...,''p''{{ind|''k''}}. On vérifie qu'aucun ne divise ''m''. Ensuite, on calcule <math>m^{\varphi(n)/p_i}\mod n \qquad\mbox{  pour } i=1,\ldots,k</math> en utilisant par exemple la méthode d'[[exponentiation rapide]]. L'entier ''m'' est une racine primitive si et seulement si ces ''k'' résultats sont tous différents de 1.}}

== Propriétés ==
* Les racines primitives mod ''n'' sont les [[Racine d'un polynôme|racines]] dans ℤ/''n''ℤ du φ(''n'')-ième [[polynôme cyclotomique]] Φ{{ind|φ(''n'')}}.

* Pour tout nombre premier ''p'', le ''n''-ième polynôme cyclotomique Φ{{ind|''n''}} est [[Polynôme irréductible|irréductible]] sur le [[corps fini]] '''Z'''{{ind|''p''}} si et seulement si ''p'' est une racine primitive modulo ''n''. Par conséquent, les entiers ''n'' modulo pour lesquels il n'existe pas de racine primitive ({{OEIS|id=A033949}}) sont ceux tels que Φ{{ind|''n''}} est réductible sur tous les '''Z'''{{ind|''p''}}. Ce sont également les entiers modulo lesquels 1 a d'autres [[Racine carrée|racines carrées]] que 1 et –1.

* Le nombre de racines primitives modulo ''n'' ({{OEIS|id=A046144}}), lorsqu'il en existe (suite {{OEIS2C|id=A033948}}), est égal à φ(φ(''n'')), puisque tout groupe cyclique d'ordre ''r'' possède φ(''r'') générateurs.

Supposons que {{mvar|p}} soit un nombre premier impair.

* Si ''θ'' est une racine primitive modulo {{mvar|p}}, alors ''θ'' est une racine primitive modulo n'importe quelle puissance {{mvar|p{{exp|k}}}} de {{mvar|p}}, sauf si ''θ''{{exp|{{mvar|p}}−1}} ≡ 1 (mod {{mvar|p}}{{exp|2}}); Dans ce cas, {{nobr|''θ'' + {{mvar|p}}}} possède cette propriété<ref>Cohen, Henri (1993). ''A Course in Computational Algebraic Number Theory''. Berlin: Springer. {{p.|26}} {{ISBN|978-3-540-55640-4}}.</ref>.

* Si ''θ'' est une racine primitive modulo {{mvar|p{{exp|k}}}}, alors ''θ'' est une racine primitive modulo toute puissance inférieure de {{mvar|p}}.

* Si ''θ'' est une racine primitive modulo {{mvar|p{{exp|k}}}}, alors ''θ'' ou ''θ'' + {{mvar|p{{exp|k}}}} (celui des deux qui est impair) est une racine primitive modulo 2{{mvar|p{{exp|k}}}}<ref>voir référence en note précédente.</ref>

Pour tout nombre premier ''p'', notons ''g<sub>p</sub>'' la plus petite racine primitive modulo ''p'' (entre 1 et ''p'' – 1). On a les deux résultats suivants :
* pour tout ε > 0, il existe<ref>{{Ouvrage|langue=en|auteur1=[[Paulo Ribenboim]]|titre=The New Book of Prime Number Records|éditeur=[[Springer Science+Business Media|Springer]]|année=1996|pages totales=541|passage=24|isbn=978-0-387-94457-9}}.</ref> une constante ''C'' telle que pour tout ''p'', {{nobr|''g<sub>p</sub> < C p''{{exp|1/4+ε}} ;}}
* si l'[[Hypothèse de Riemann généralisée|hypothèse généralisée de Riemann]] est vraie, alors<ref>{{Ouvrage|langue=en|auteur1={{Lien|Eric Bach}}|auteur2=[[Jeffrey Shallit]]|titre=Algorithmic Number Theory|volume=I|titre volume=Efficient Algorithms|éditeur=[[MIT Press]]|année=1996|pages totales=512|passage=254|isbn=978-0-262-02405-1|lire en ligne=https://books.google.com/books?id=iJx1lP9ZcIkC&printsec=frontcover}}.</ref> ''g<sub>p</sub>'' = [[Notation de Landau|O]]([[Logarithme|log]]{{6}} ''p'').

On conjecture que tout [[entier relatif]] différent de –1 et non [[Carré parfait|carré]] est racine primitive modulo une infinité de nombres premiers (voir « [[Conjecture d'Artin sur les racines primitives]] »).

== Notes et références ==
{{Traduction/Référence|en|Primitive root modulo n|630813756|type=note}}
{{Références}}

== Voir aussi ==
=== Article connexe ===
[[Racine de l'unité modulo n|Racine de l'unité modulo ''n'']]

=== Bibliographie ===
{{Chapitre|lang=en|titre ouvrage=Number Theoretic Methods|page=219-231|titre=Primitive Roots: A Survey|auteur=Shuguang Li|auteur2=[[Carl Pomerance]]|année=2002|url=https://math.dartmouth.edu/~carlp/PDF/primitiverootstoo.pdf|format électronique=pdf|éditeur=[[Springer Verlag|Springer]]}}

{{Portail|nombre}}

[[Catégorie:Arithmétique modulaire]]