Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

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 entre eux à n, pris modulo n, forment un groupe muni de la multiplication ; écrit sous la forme (Z/nZ)^× ou Z_n^*. Ce groupe est cyclique si et seulement si n est égal à 1 ou 2 ou 4 ou p^k ou 2 p^k 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 Z_n^*. Une racine primitive module n est thus un entier g tel que, modulo n, chaque autre entier est juste 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 nous avons 3² = 9, 3³ = 13, 3⁴ = 11, 3⁵ = 5 et 3⁶ = 1 (modulo 14). Les seules autres racines primitives modulo 14 est 5.

Voici une table contenant les plus petites racines primitives pour diverses valeurs de n (voir A046145 ):

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 p₁,...,p_k. 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 p₀ telles que, pour chaque nombre premier p ≥ p₀, il existe une racine primitive modulo p qui est plus petite que C p^1/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))².

Voir aussi : conjecture d'Artin.