Les racines primitives modulo n, . 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 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 Z. Ce groupe est cyclique si et seulement si n est égal à 4 ou p ou 2p pour un nombre premier p ≥ 3 et k ≥ 0Une démonstration est donnée dans l'article « Anneau Z/nZ », § « Groupe des unités ».. Un générateur de ce groupe cyclique est appelé une racine primitive modulo n, ou un élément primitif. de Z. 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 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 3 ≡ 9, 3 ≡ 13, 3 ≡ 11, 3 ≡ 5 et 3 ≡ 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 () : n234567891011121314racine primitive mod n123253-232-23
Voici une table donnant les plus petites racines primitives r modulo les nombres premiers p inférieurs à ()Table des racines primitives des premiers nombres premiers. :
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 2 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 On ne connaît 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 Z) — qui est plus rapide qu'un simple calcul mod n de toutes ses puissances successives jusqu'à l'exposant φ(n) :
Propriétés Les racines primitives mod n sont les racines dans ℤ/nℤ du φ(n)-ième polynôme cyclotomique Φ.
Pour tout nombre premier p, le n-ième polynôme cyclotomique Φ est irréductible sur le corps fini Z si et seulement si p est une racine primitive modulo n. Par conséquent, les entiers n modulo pour lesquels il n'existe pas de racine primitive () sont ceux tels que Φ est réductible sur tous les Z. 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 (), lorsqu'il en existe (suite ), est égal à φ(φ(n)), puisque tout groupe cyclique d'ordre r possède φ(r) générateurs.
Supposons que soit un nombre premier impair.
Si θ est une racine primitive modulo , alors θ est une racine primitive modulo n'importe quelle puissance de , sauf si θ ≡ 1 (mod ); Dans ce cas, possède cette propriétéCohen, Henri (1993). A Course in Computational Algebraic Number Theory. Berlin: Springer. ..
Si θ est une racine primitive modulo , alors θ est une racine primitive modulo toute puissance inférieure de .
Si θ est une racine primitive modulo , alors θ ou θ + (celui des deux qui est impair) est une racine primitive modulo 2voir référence en note précédente.
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 : pour tout ε > 0, il existe. une constante C telle que pour tout p, si l'hypothèse généralisée de Riemann est vraie, alors. gp = O(log p).
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
Voir aussi Articles connexes Racine de l'unité modulo n
Bibliographie
Catégorie:Arithmétique modulaire