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 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 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 n^iè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 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 (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 p₁,...,p_k. Maintenant, pour chaque élément m de (Z/nZ)^×, calculons

$m^{\phi(n)/p_i}\mod n \qquad\mbox{ for } i=1,\ldots,k$

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.

Ce document provient de « Racine primitive modulo n ».