Racine primitive modulo n

Les racines primitives modulo n^[1] 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_n^×. Ce groupe est cyclique si et seulement si n est égal à 4 ou p^k ou 2p^k pour un nombre premier p ≥ 3 et k ≥ 0^[2]. Un générateur de ce groupe cyclique est appelé une racine primitive modulo n, ou un élément primitif^[3] de Z_n^×. 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 (suite A046145 de l'OEIS) :

n	2	3	4	5	6	7	8	9	10	11	12	13	14
racine primitive mod n	1	2	3	2	5	3	-	2	3	2	-	2	3

Voici une table donnant les plus petites racines primitives r modulo les nombres premiers p inférieurs à 1 000 (suite A001918 de l'OEIS)^[4] :

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	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	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 connait 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_n^×) — qui est plus rapide qu'un simple calcul mod n de toutes ses puissances successives jusqu'à l'exposant φ(n) :

On a au préalable calculé φ(n) et déterminé ses diviseurs premiers, soit p₁,...,p_k. On vérifie qu'aucun ne divise m. Ensuite, on calcule $m^{\varphi (n)/p_{i}}\mod n\qquad {\mbox{ pour }}i=1,\ldots ,k$ en utilisant par exemple la méthode d'exponentiation rapide. L'entier m est une racine primitive si et seulement si ces k résultats sont tous différents de 1.

Propriétés

Les racines primitives mod n sont les racines dans ℤ/nℤ du φ(n)-ième polynôme cyclotomique Φ_φ(n).

Pour tout nombre premier p, le n-ième polynôme cyclotomique Φ_n est irréductible sur le corps fini Z_p 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 (suite A033949 de l'OEIS) sont ceux tels que Φ_n est réductible sur tous les Z_p. 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 (suite A046144 de l'OEIS), lorsqu'il en existe (suite A033948), est égal à φ(φ(n)), puisque tout groupe cyclique d'ordre r possède φ(r) générateurs.

Supposons que $p$ soit un nombre premier impair.

Si θ est une racine primitive modulo $p$ , alors θ est une racine primitive modulo n'importe quelle puissance $p k$ de $p$ , sauf si θ^{$p$ −1} ≡ 1 (mod $p$ ²); Dans ce cas, θ + $p$ possède cette propriété^[5].

Si θ est une racine primitive modulo $p k$ , alors θ est une racine primitive modulo toute puissance inférieure de $p$ .

Si θ est une racine primitive modulo $p k$ , alors θ ou θ + $p k$ (celui des deux qui est impair) est une racine primitive modulo 2 $p k$ ^[6]

Pour tout nombre premier p, notons g_p la plus petite racine primitive modulo p (entre 1 et p – 1). On a les deux résultats suivants :

pour tout ε > 0, il existe^[7] une constante C telle que pour tout p, g_p < C p^1/4+ε ;
si l'hypothèse généralisée de Riemann est vraie, alors^[8] g_p = 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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Primitive root modulo n » (voir la liste des auteurs).

↑ Carl Friedrich Gauss, Disquisitiones arithmeticae, 1801 [détail des éditions], § 54-57.
↑ Une démonstration est donnée dans l'article « Anneau Z/nZ », § « Groupe des unités ».
↑ (en) D. Rasch, J. Pilz, R. Verdooren et A. Gebhardt, Optimal Experimental Design with R, Taylor & Francis, coll. « Chapman & Hall/CRC Press », 2011 (lire en ligne), p. 291.
↑ Table des racines primitives des 10 000 premiers nombres premiers.
↑ Cohen, Henri (1993). A Course in Computational Algebraic Number Theory. Berlin: Springer. p. 26 (ISBN 978-3-540-55640-4).
↑ voir référence en note précédente.
↑ (en) Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, 541 p. (ISBN 978-0-387-94457-9), p. 24.
↑ (en) Eric Bach (en) et Jeffrey Shallit, Algorithmic Number Theory, vol. I : Efficient Algorithms, MIT Press, 1996, 512 p. (ISBN 978-0-262-02405-1, lire en ligne), p. 254.

Voir aussi

Article connexe

Racine de l'unité modulo n

Bibliographie

(en) Shuguang Li et Carl Pomerance, « Primitive Roots: A Survey », dans Number Theoretic Methods, Springer, 2002 (lire en ligne [PDF]), p. 219-231

Arithmétique et théorie des nombres

[1] Carl Friedrich Gauss, Disquisitiones arithmeticae, 1801 [détail des éditions], § 54-57.

[2] Une démonstration est donnée dans l'article « Anneau Z/nZ », § « Groupe des unités ».

[3] (en) D. Rasch, J. Pilz, R. Verdooren et A. Gebhardt, Optimal Experimental Design with R, Taylor & Francis, coll. « Chapman & Hall/CRC Press », 2011 (lire en ligne), p. 291.

[4] Table des racines primitives des 10 000 premiers nombres premiers.

[5] Cohen, Henri (1993). A Course in Computational Algebraic Number Theory. Berlin: Springer. p. 26 (ISBN 978-3-540-55640-4).

[6] voir référence en note précédente.

[7] (en) Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, 541 p. (ISBN 978-0-387-94457-9), p. 24.

[8] (en) Eric Bach (en) et Jeffrey Shallit, Algorithmic Number Theory, vol. I : Efficient Algorithms, MIT Press, 1996, 512 p. (ISBN 978-0-262-02405-1, lire en ligne), p. 254.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

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	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	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

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	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	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

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	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	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