- Racine Primitive Modulo N
-
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≥1 est un entier, les nombres premiers avec n, pris modulo n, forment un groupe muni de 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 module 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 (voir A046145):
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 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 candidates. Si l'ordre multiplicatif d'un nombre m modulo n est égal à φ(n) (l'ordre de Z/nZ), 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
utilisant la rapide exponentiation par carré. 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.
Quelquefois, on peut être intéressé par les petites racines primitives. Nous avons les résultats suivants. Pour chaque ε>0 il existe des constantes positives C et p0 telles que, pour chaque nombre premier p ≥ p0, il existe une racine primitive modulo p qui est plus petite que C p1/4+ε. Si l'hypothèse généralisée de Riemann est vraie, alors pour chaque nombre premier p, il existe une racine primitive modulo p qui est inférieure à 70 (ln(p))2.
Voir aussi : conjecture d'Artin.
Portail des mathématiques
Catégorie : Arithmétique modulaire
Wikimedia Foundation. 2010.
