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 sont un concept issu de l'arithmétique modulaire, dans la théorie des nombres.

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[1]. Un générateur de ce groupe cyclique est appelé une racine primitive modulo n, ou un élément primitif[2] de Zn*. Une racine primitive modulo n est donc un entier g tel que, modulo n, chaque autre entier qui est inversible, modulo n, dans Z/nZ est simplement une puissance de g.

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 des nombres premiers p inférieurs à 1000 (suite A001918 de l'OEIS)[3] :

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

Aucune formule générale simple pour calculer les racines primitives modulo n n'est connue. Il existe néanmoins une méthode pour localiser une racine primitive qui est plus rapide qu'un simple essai de tous les candidats. Si l'ordre multiplicatif d'un nombre m modulo n est égal à φ(n) (l'ordre de Zn*), alors m est une racine primitive. On peut utiliser ceci pour tester les racines primitives :

On calcule d'abord φ(n), puis on détermine ses diviseurs premiers, soit p1,...,pk. Ensuite pour chaque élément m de (Z/nZ)×, on calcule

en utilisant par exemple la méthode d'exponentiation rapide. Dès qu'on trouve un nombre m pour lequel ces k résultats sont tous différents de 1, on arrête : m est une racine primitive.

Le nombre de racines primitives modulo n 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 :

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. Une démonstration est donnée dans l'article « Anneau Z/nZ », § « Groupe des unités ».
  2. (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.
  3. Table des racines primitives des 10 000 premiers nombres premiers.
  4. (en) Paulo Ribenboim, The New Book of Prime Number Records, Springer, (ISBN 978-0-387-94457-9), p. 24.
  5. (en) Eric Bach (en) et Jeffrey Shallit, Algorithmic Number Theory, vol. I : Efficient Algorithms, MIT Press, (ISBN 978-0-262-02405-1), p. 254.

Articles connexes[modifier | modifier le code]