# Racine primitive modulo n

Les racines primitives modulo n sont un concept issu de l'arithmétique modulaire, dans la théorie des nombres. Ce sont (lorsqu'il en existe) les générateurs du groupe des inversibles de l'anneau ℤ/nℤ.

## Définition

Si n est un entier strictement positif, les nombres premiers avec n, pris modulo n, forment un groupe pour la multiplication, noté (Z/nZ)$^×$ ou Z$_n$$^×$. Ce groupe est cyclique si et seulement si n est égal à 4 ou p$^k$ ou 2p$^k$ pour un nombre premier p ≥ 3 et k ≥ 0. Un générateur de ce groupe cyclique est appelé une racine primitive modulo n, ou un élément primitif de Z$_n$$^×$. Une racine primitive modulo n est donc un entier g tel que tout inversible dans Z/nZ est une puissance de g modulo n.

## Exemples

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

## 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 à φ(n) (l'ordre de Z$_n$$^×$) — qui est plus rapide qu'un simple calcul mod n de toutes ses puissances successives jusqu'à l'exposant φ(n) :
On a au préalable calculé φ(n) et déterminé ses diviseurs premiers, soit p$_1$,...,p$_k$. On vérifie qu'aucun ne divise m. Ensuite, on calcule $m^{\varphi (n)/p_{i}}\mod n\qquad {\mbox{ pour }}i=1,\ldots ,k$ 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 racines dans ℤ/nℤ du φ(n)-ième polynôme cyclotomique Φ$_{φ(n)}$.
* Pour tout nombre premier p, le n-ième polynôme cyclotomique Φ$_n$ est irréductible sur le corps fini Z$_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 (suite A033949 de l'OEIS) sont ceux tels que Φ$_n$ est réductible sur tous les Z$_p$. Ce sont également les entiers modulo lesquels 1 a d'autres racines carrées que 1 et –1.
* Le nombre de racines primitives modulo n (suite A046144 de l'OEIS), lorsqu'il en existe (suite  A033948), est égal à φ(φ(n)), puisque tout groupe cyclique d'ordre r possède φ(r) générateurs.
Supposons que p soit un nombre premier impair.
* Si θ est une racine primitive modulo p, alors θ est une racine primitive modulo n'importe quelle puissance p$^k$ de p, sauf si θ$^{p−1}$ ≡ 1 (mod p$^2$); Dans ce cas, θ + p possède cette propriété.
* Si θ est une racine primitive modulo p$^k$, alors θ est une racine primitive modulo toute puissance inférieure de p.
* Si θ est une racine primitive modulo p$^k$, alors θ ou θ + p$^k$ (celui des deux qui est impair) est une racine primitive modulo 2p$^k$
Pour tout nombre premier p, notons g$_p$ la plus petite racine primitive modulo p (entre 1 et p – 1). On a les deux résultats suivants :
* pour tout ε > 0, il existe une constante C telle que pour tout p, g$_p$ < C p$^{1/4+ε}$ ;
* si l'hypothèse généralisée de Riemann est vraie, alors g$_p$ = O(log$^6$ p).
On conjecture que tout entier relatif différent de –1 et non carré est racine primitive modulo une infinité de nombres premiers (voir « Conjecture d'Artin sur les racines primitives »).