Racine primitive modulo n

Ensembles des éléments de l'anneau Z/nZ premiers avec n, donc générateurs du groupe des unités de cet anneau

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.

DéfinitionModifier

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.

ExemplesModifier

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 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)[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
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

CalculModifier

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ésModifier

  • 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érencesModifier

(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 aussiModifier

Article connexeModifier

Racine de l'unité modulo n

BibliographieModifier

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