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\) ? Indication : calculer les puissances successives de \(2\) et de \(3\) modulo \(7\).
- Trouver toutes les racines primitives modulo \(11\). Indication : si \(g\) est une racine primitive, les autres sont les \(g^k\) avec \(\gcd(k, 10) = 1\) ; tester \(g = 2\).
- Soit \(q\) un nombre premier et \(p\) un nombre premier qui divise \(2^q - 1\). Montrer que \(p \equiv 1 \pmod q\). Indication : l'ordre de \(2\) modulo \(p\) divise \(q\) et ne vaut pas \(1\), et il divise \(p - 1\).
- Soit \(p\) un nombre premier qui divise \(a^4 + 1\) pour un entier \(a\). Montrer que \(p = 2\) ou \(p \equiv 1 \pmod 8\). Indication : si \(p\) est impair, \(a^4 \equiv -1\) et \(a^8 \equiv 1 \pmod p\) : quel est l'ordre de \(a\) ?
- Montrer que si \(n \geq 1\) divise \(2^n - 1\), alors \(n = 1\). Indication : le plus petit diviseur premier de \(n\).
Parcours suggéré¶
Un choix de problèmes de la shortlist, du plus accessible au plus difficile, où ce concept joue le premier rôle. La liste complète est plus bas.
Étape 1 — Premiers pas (1 ★)
La shortlist n'a pas de problème de ce niveau sur ce thème : les exercices d'échauffement en tiennent lieu.
Étape 2 — Consolidation (2 ★)
- 2006 N2 ★★☆☆☆ : On garde les chiffres de rang \(2^n\) dans le développement décimal d'un rationnel : le nombre obtenu est encore rationnel.
- 2017 N4 ★★☆☆☆ : Combien d'exposants \(t\) minimaux peuvent rendre \((10^t - 1)/(cm)\) décimal, lorsque \(c\) parcourt \(1, \ldots, 2017\) ?
- 2023 N3 ★★☆☆☆ : Dans \(n!\), la plus grande puissance de \(10\) dépasse parfois celle de \(9\), et parfois non, une infinité de fois chacune.
Étape 3 — Approfondissement (3 ★)
- 2006 N5 ★★★☆☆ : Résoudre en entiers \((x^7 - 1)/(x - 1) = y^5 - 1\).
- 2020 N4 ★★★☆☆ : Des suites où l'on ajoute à chaque terme son reste modulo \(p\) : peuvent-elles se dépasser l'une l'autre indéfiniment ?
Étape 4 — Défi (4 ★ – 5 ★)
- 2011 N6 ★★★★☆ : Si \(2^{Q(n)} - 1\) divise toujours \(3^{P(n)} - 1\), pour des polynômes sans facteur commun, alors \(Q\) est constant.
- 2012 N6 ★★★★☆ : Si \(2^n y + 1\) divise \(x^{2^n} - 1\) pour tout \(n\), alors \(x = 1\).
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¶
La shortlist compte très peu de problèmes faciles sur ce thème : si le concept est nouveau pour vous, commencez par les exercices d'échauffement ci-dessus.
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 |