- Racine primitive modulo n
-
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 impair p 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 juste une puissance de g. La démonstration est donnée dans le paragraphe Groupe des unités de l'article Anneau Z/nZ.
Cette définition s'applique aussi aux nombres complexes de module un. Une racine primitive d'ordre n, si n est un entier positif est une racine nième tel que ses puissances engendrent toutes les racines d'ordre n.
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 racine primitive mod n 2 1 3 2 4 3 5 2 6 5 7 3 8 - 9 2 10 3 11 2 12 - 13 2 14 3 Voici une table donnant les plus petites racines primitives des nombres premiers inférieurs à mille (suite A001918 de l’OEIS) :
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 7 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 7 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 2 653 2 751 3 853 2 947 2 19 2 79 3 151 6 229 6 311 11 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 3 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 2 31 3 97 5 167 5 241 7 331 2 419 2 499 7 599 7 677 2 773 2 877 2 977 3 37 2 101 2 173 2 251 2 337 10 421 2 503 5 601 7 683 2 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
en utilisant par exemple la méthode d'exponentiation rapide. Dès que nous trouvons un nombre m pour lequel ces k résultants 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).
Voir aussi
Wikimedia Foundation. 2010.
