Racine primitive modulo n

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les racines primitives complexes de l'unité, voir Racine de l'unité.

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éfinition[modifier | modifier le code]

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[modifier | modifier le code]

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

Calcul[modifier | modifier le code]

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[modifier | modifier le code]

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

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[modifier | modifier le code]

(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. (en) Paulo Ribenboim, The New Book of Prime Number Records, Springer, (ISBN 978-0-387-94457-9), p. 24.
  6. (en) Eric Bach (en) et Jeffrey Shallit, Algorithmic Number Theory, vol. I : Efficient Algorithms, MIT Press, (ISBN 978-0-262-02405-1), p. 254.

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Racine de l'unité modulo n (en)

Bibliographie[modifier | modifier le code]

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