Racine primitive modulo n

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur les redirections 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, écrit sous la forme (Z/nZ)× ou Zn*. Ce groupe est cyclique si et seulement si n est égal à 1 ou 2 ou 4 ou pk ou 2 pk pour un nombre premier p ≥ 3 et k ≥ 1. Un générateur de ce groupe cyclique est appelé une racine primitive modulo n, ou un élément primitif de Zn*. Une racine primitive modulo n est donc un entier g tel que, modulo n, chaque autre entier est simplement une puissance de g. La démonstration est donnée dans le paragraphe Groupe des unités de l'article Anneau Z/nZ.

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 nous avons 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)[1] :

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 des méthodes 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 il est une racine primitive. Nous pouvons utiliser ceci pour tester les racines primitives :

premièrement calculons φ(n). Puis, déterminons les différents facteurs premiers de φ(n), soit p1,...,pk. Maintenant, pour chaque élément m de (Z/nZ)×, calculons
m^{\phi(n)/p_i}\mod n \qquad\mbox{  pour } i=1,\ldots,k

en utilisant par exemple la méthode d'exponentiation rapide. Dès que nous trouvons un nombre m pour lequel ces k résultats sont tous différents de 1, nous stoppons : m est une racine primitive.

Le nombre de racines primitives modulo n est égal à φ(φ(n)) comme, en général, un groupe cyclique de r éléments 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). Nous avons les résultats suivants. Pour chaque ε>0 il existe une constante C telle que pour tout p, gp < C p1/4+ε. Si l'hypothèse généralisée de Riemann est vraie, alors gp = O(ln6 p).

Notes et références[modifier | modifier le code]

Voir aussi[modifier | modifier le code]