Racine primitive modulo n

Les racines primitives modulo n[1] 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.

Pour les racines primitives complexes de l'unité, voir Racine de l'unité.

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 Zn×. Ce groupe est cyclique si et seulement si n est égal à 4 ou pk ou 2pk pour un nombre premier p ≥ 3 et k ≥ 0[2]. Un générateur de ce groupe cyclique est appelé une racine primitive modulo n, ou un élément primitif[3] de Zn×. 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 32 ≡ 9, 33 ≡ 13, 34 ≡ 11, 35 ≡ 5 et 36 ≡ 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 234567891011121314
racine primitive mod n 123253-232-23

Voici une table donnant les plus petites racines primitives r modulo les nombres premiers p inférieurs à 1 000 (suite A001918 de l'OEIS)[4] :

p r p r p r p r p r p r p r p r p r p r p r p r
21 475 1096 19119 2692 3533 43915 5232 6173 7092 8113 9072
32 532 1133 1935 2716 3597 4432 5412 6192 71911 8212 91117
52 592 1273 1972 2775 3676 4493 5472 6313 7275 8233 9197
73 612 1312 1993 2813 3732 45713 5572 6413 7336 8272 9293
112 672 1373 2112 2833 3792 4612 5632 64311 7393 8292 9375
132 717 1392 2233 2932 3835 4633 5693 6475 7435 83911 9412
173 735 1492 2272 3075 3892 4672 5713 6532 7513 8532 9472
192 793 1516 2296 31117 3975 47913 5775 6592 7572 8573 9533
235 832 1575 2333 31310 4013 4873 5872 6612 7616 8592 9675
292 893 1632 2397 3172 40921 4912 5933 6735 76911 8635 9716
313 975 1675 2417 3313 4192 4997 5997 6772 7732 8772 9773
372 1012 1732 2516 33710 4212 5035 6017 6835 7872 8813 9835
416 1035 1792 2573 3472 4317 5092 6073 6913 7972 8832 9916
433 1072 1812 2635 3492 4335 5213 6132 7012 8093 8875 9977

Calcul

On ne connait 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 Zn×) — 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 p1,...,pk. On vérifie qu'aucun ne divise m. Ensuite, on calcule 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

  • Pour tout nombre premier p, le n-ième polynôme cyclotomique Φn est irréductible sur le corps fini Zp si et seulement si p est une racine primitive modulo n. Par conséquent, les entiers n modulo lesquels il n'existe pas de racine primitive (suite A033949 de l'OEIS) sont ceux tels que Φn est réductible sur tous les Zp. 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 pk de p, sauf si θp−1 ≡ 1 (mod p2); Dans ce cas, θ + p possède cette propriété[5].
  • Si θ est une racine primitive modulo pk, alors θ est une racine primitive modulo toute puissance inférieure de p.
  • Si θ est une racine primitive modulo pk, alors θ ou θ + pk (celui des deux qui est impair) est une racine primitive modulo 2pk[6]

Pour tout nombre premier p, notons gp la plus petite racine primitive modulo p (entre 1 et p – 1). On a les deux résultats suivants :

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 »).

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Primitive root modulo n » (voir la liste des auteurs).
  1. Carl Friedrich Gauss, Disquisitiones arithmeticae, [détail des éditions], § 54-57.
  2. Une démonstration est donnée dans l'article « Anneau Z/nZ », § « Groupe des unités ».
  3. (en) D. Rasch, J. Pilz, R. Verdooren et A. Gebhardt, Optimal Experimental Design with R, Taylor & Francis, coll. « Chapman & Hall/CRC Press », (lire en ligne), p. 291.
  4. Table des racines primitives des 10 000 premiers nombres premiers.
  5. Cohen, Henri (1993). A Course in Computational Algebraic Number Theory. Berlin: Springer. p. 26 (ISBN 978-3-540-55640-4).
  6. voir référence en note précédente.
  7. (en) Paulo Ribenboim, The New Book of Prime Number Records, Springer, , 541 p. (ISBN 978-0-387-94457-9), p. 24.
  8. (en) Eric Bach (en) et Jeffrey Shallit, Algorithmic Number Theory, vol. I : Efficient Algorithms, MIT Press, , 512 p. (ISBN 978-0-262-02405-1, lire en ligne), p. 254.

Voir aussi

Article connexe

Racine de l'unité modulo n

Bibliographie

(en) Shuguang Li et Carl Pomerance, « Primitive Roots: A Survey », dans Number Theoretic Methods, Springer, (lire en ligne [PDF]), p. 219-231

  • Arithmétique et théorie des nombres
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.