Ordre d'un élément et racines primitives¶
Domaine : Théorie des nombres · Niveau : intermédiaire · Prérequis : Congruences, Fermat et Euler
L'idée¶
Soit \(a\) un entier premier avec \(n\). Les puissances \(a, a^2, a^3, \ldots\) modulo \(n\) finissent par revenir à \(1\) (par le théorème d'Euler, \(a^{\varphi(n)} \equiv 1\)). L'ordre de \(a\) modulo \(n\), noté \(\operatorname{ord}_n(a)\), est le plus petit entier \(k \geq 1\) tel que \(a^k \equiv 1 \pmod n\). Par exemple, modulo \(7\), les puissances de \(2\) sont \(2, 4, 1, 2, 4, 1, \ldots\), donc \(\operatorname{ord}_7(2) = 3\).
Tout repose sur un lemme :
Pourquoi. Écrivons \(m = qk + r\) avec \(k = \operatorname{ord}_n(a)\) et \(0 \leq r < k\). Alors \(a^m = (a^k)^q a^r \equiv a^r\). Si \(a^m \equiv 1\), alors \(a^r \equiv 1\) avec \(r < k\), donc \(r = 0\) par minimalité de \(k\).
Conséquences immédiates :
- \(\operatorname{ord}_n(a)\) divise \(\varphi(n)\) ; en particulier, pour \(p\) premier, \(\operatorname{ord}_p(a)\) divise \(p - 1\) ;
- les puissances de \(a\) modulo \(n\) sont périodiques de période exactement \(\operatorname{ord}_n(a)\) ;
- si \(a^m \equiv 1\) et \(a^{m'} \equiv 1\), alors \(a^{\operatorname{pgcd}(m, m')} \equiv 1\).
L'usage principal est de contraindre les diviseurs premiers de \(a^k - 1\) ou \(a^k + 1\) : si \(p\) divise \(a^k - 1\), alors \(\operatorname{ord}_p(a)\) divise à la fois \(k\) et \(p - 1\).
Racines primitives¶
Un entier \(g\) est une racine primitive modulo \(n\) si son ordre vaut \(\varphi(n)\), le maximum possible. Les racines primitives existent modulo tout nombre premier \(p\) (il y en a \(\varphi(p - 1)\)), et plus généralement modulo \(2\), \(4\), \(p^k\) et \(2p^k\) pour \(p\) premier impair, et seulement pour ces modules.
Modulo un premier \(p\), si \(g\) est une racine primitive, les restes non nuls sont exactement \(g^0, g^1, \ldots, g^{p-2}\). Écrire \(x \equiv g^i\) transforme les produits en sommes d'exposants modulo \(p - 1\). Par exemple, \(x^d \equiv 1 \pmod p\) a exactement \(\operatorname{pgcd}(d, p - 1)\) solutions.
Exemple résolu¶
Problème
Soit \(n \geq 0\) et \(p\) un nombre premier qui divise \(2^{2^n} + 1\). Montrer que \(p \equiv 1 \pmod{2^{n+1}}\).
Étape 1 : traduire. \(p\) est impair, car \(2^{2^n} + 1\) l'est. On a \(2^{2^n} \equiv -1 \pmod p\), donc en élevant au carré, \(2^{2^{n+1}} \equiv 1 \pmod p\).
Étape 2 : encadrer l'ordre. Soit \(k = \operatorname{ord}_p(2)\). Par le lemme, \(k\) divise \(2^{n+1}\), donc \(k\) est une puissance de \(2\). Si \(k\) divisait \(2^n\), on aurait \(2^{2^n} \equiv 1\) ; or \(2^{2^n} \equiv -1\), et \(-1 \not\equiv 1\) car \(p \neq 2\). Donc \(k = 2^{n+1}\) exactement.
Étape 3 : conclure avec Fermat. L'ordre divise \(p - 1\) : \(2^{n+1}\) divise \(p - 1\), c'est-à-dire \(p \equiv 1 \pmod{2^{n+1}}\).
Par exemple, \(2^{32} + 1 = 641 \times 6\,700\,417\), et \(641 = 5 \times 2^7 + 1\) est bien \(\equiv 1 \pmod{64}\).
Le schéma est toujours le même : une congruence \(a^m \equiv \pm 1\) coince l'ordre (il divise \(m\) ou \(2m\), mais pas moins), puis l'ordre divise \(p - 1\).
Comment le reconnaître¶
- Des expressions \(a^n - 1\) ou \(a^n + 1\) et une question sur leurs diviseurs premiers.
- Une condition « \(n\) divise \(a^n - 1\) » ou « \(p\) divise \(a^k + 1\) ».
- Une suite définie par multiplication modulo \(p\) (\(x_{n+1} \equiv 2x_n\)), dont on cherche la période.
- Une question sur le nombre de solutions de \(x^d \equiv 1\) ou \(x^d \equiv a \pmod p\).
Techniques classiques¶
| Situation | Technique |
|---|---|
| \(a^m \equiv 1 \pmod n\) | \(\operatorname{ord}_n(a)\) divise \(m\) |
| \(p\) premier divise \(a^k - 1\) | \(\operatorname{ord}_p(a)\) divise \(\operatorname{pgcd}(k, p - 1)\) |
| \(p\) divise \(a^k + 1\) | \(a^{2k} \equiv 1\) mais \(a^k \not\equiv 1\) : l'ordre divise \(2k\) sans diviser \(k\) |
| « \(n\) divise \(a^n - 1\) » | Prendre le plus petit diviseur premier \(p\) de \(n\) : \(\operatorname{pgcd}(n, p - 1) = 1\) |
| Périodicité de \(a^n \bmod p\) | La période est \(\operatorname{ord}_p(a)\) |
| Ordre d'une puissance | \(\operatorname{ord}_n(a^h) = \dfrac{\operatorname{ord}_n(a)}{\operatorname{pgcd}(\operatorname{ord}_n(a), h)}\) |
| Équation \(x^d \equiv c \pmod p\) | Racine primitive : passer aux exposants modulo \(p - 1\) |
Exercices d'échauffement¶
- Calculer \(\operatorname{ord}_7(2)\) et \(\operatorname{ord}_7(3)\). Lequel est une racine primitive modulo \(7\) ?
- Trouver toutes les racines primitives modulo \(11\).
- Soit \(q\) un nombre premier et \(p\) un nombre premier qui divise \(2^q - 1\). Montrer que \(p \equiv 1 \pmod q\).
- Soit \(p\) un nombre premier qui divise \(a^4 + 1\) pour un entier \(a\). Montrer que \(p = 2\) ou \(p \equiv 1 \pmod 8\).
- Montrer que si \(n \geq 1\) divise \(2^n - 1\), alors \(n = 1\). Indication : le plus petit diviseur premier de \(n\).
L'ordre dans la shortlist¶
- 2019 N7, solution 1 : si \(p\) divise \(2^{2^{t-1}} + 1\), alors \(2^t\) divise \(p - 1\), comme dans l'exemple résolu.
- 2020 N4 : \(x_{n+1} \equiv 2x_n \pmod p\), donc les restes sont périodiques, de période l'ordre de \(2\) modulo \(p\).
- 2017 N5 : l'ordre d'un quotient modulo un premier \(r\) divise \(2q\), ce qui ne laisse que deux possibilités pour \(r\).
- 2025 N7 : l'ordre de \(5\) modulo \(2^z\) permet d'obtenir \(2^z \mid 5^{2^x} - 1\).
- 2017 N4 : l'ensemble cherché s'exprime avec les ordres de \(10\) modulo des entiers \(cm\).
Pour approfondir : Objectif Olympiades de Mathématiques, tome 5 (M. Aassila), p. 167 à 171 (définition et propriétés de l'ordre, lien avec la divisibilité p. 168), p. 172 à 180 (exemples et exercices), p. 289 à 293 (ordre multiplicatif, racines primitives p. 290, modules qui en possèdent p. 291, équations \(x^n \equiv a \pmod p\)).
Problèmes de la shortlist¶
13 problèmes · difficulté moyenne : ★★★★★ (3,4) · dont 1 choisi pour l'OIM
Répartition par difficulté : 1 ★ : 0 · 2 ★ : 3 · 3 ★ : 4 · 4 ★ : 4 · 5 ★ : 2
| Problème | Difficulté | Concepts |
|---|---|---|
| 2023 N3 | ★★☆☆☆ | Valuations p-adiques et lemme LTE · Partie entière et majorations |
| 2017 N4 | ★★☆☆☆ | Valuations p-adiques et lemme LTE |
| 2006 N2 | ★★☆☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2020 N4 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme |
| 2017 N5 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Congruences, théorèmes de Fermat et d'Euler |
| 2010 N2 | ★★★☆☆ | Équations diophantiennes : factorisation et encadrement · Divisibilité, PGCD et algorithme d'Euclide |
| 2006 N5 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2025 N7 · OIM P3 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler · Valuations p-adiques et lemme LTE |
| 2019 N7 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler · Théorème des restes chinois |
| 2012 N6 | ★★★★☆ | Résidus quadratiques · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Théorème des restes chinois |
| 2011 N6 | ★★★★☆ | Polynômes à coefficients entiers · Divisibilité, PGCD et algorithme d'Euclide |
| 2012 N8 | ★★★★★ | Double comptage · Résidus quadratiques · Cauchy-Schwarz et lemme de Titu |
| 2011 N8 | ★★★★★ | Résidus quadratiques · Graphes : degrés, chemins, arbres |