Chapitre extrait du Tome 5 — Arithmétique du livre « Objectif Olympiades de Mathématiques » de Mohammed Aassila. Réservé aux élèves se préparant aux concours d'olympiades de niveau lycée.

7.1 Définition. Propriétés

Soient $a$ et $n$ des entiers tels que $n>1$ et $\gcd (a,n)=1$. On sait, d'après le théorème d'Euler, qu'il existe toujours (au moins) un entier naturel $k$ vérifiant $a^k\equiv 1(\mathrm{mod}n)$, à savoir, $k=\varphi (n)$. Cependant, rien de ce que nous avons fait jusqu'à présent ne garantit que $\varphi (n)$ est le plus petit de tels $k$. Par exemple $2^3\equiv 1(\mathrm{mod}7)$, même si $\varphi (7)=6$. Ces considérations motivent la définition suivante :

Définition

Soient $a$ et $n>1$ deux entiers premiers entre eux. L'ordre de $a$, modulo $n$, noté ${\text{ord}}_n(a)$, est le plus petit $h\in {\mathbb{N}}^{\ast }$ possible tel que :

$$a^h\equiv 1(\mathrm{mod}n).$$

On a clairement : ${\text{ord}}_n(a)\le \varphi (n)$.

Remarque : Notons que ${\text{ord}}_n(a)$ n'est pas défini lorsque $\gcd (a,n)\ne 1$.

Remarque : La suite des restes modulo $n$ des nombres $1,a,a^2,\cdots$ est périodique de période minimale ${\text{ord}}_n(a)$. Ceci découle du fait que $a^i\equiv a^{i+j}(\mathrm{mod}n)$ est équivalente (d'après le lemme de Gauss) à : $a^j\equiv 1(\mathrm{mod}n)$ pour tout $i,j\in {\mathbb{N}}^{\ast }$. Par exemple, pour $a=3$ et $n=17$, la suite des restes modulo $n=17$ de $1,a,a^2,\dots$ est :

$$1,3,9,10,13,5,15,11,16,14,8,7,4,12,2,6,\underbrace{1,3,9,10,\cdots }$$

et la longueur de la période est $16$, donc ${\text{ord}}_{17}(3)=16$.

Proposition

Soient $a,n\in \mathbb{Z}$, avec $n>1$ et $\gcd (a,n)=1$.

1. Si ${\text{ord}}_n(a)=h$, alors les entiers $1,a,a^2,\cdots ,a^{h-1}$ sont $2$ à $2$ non congrus modulo $n$.
2. Les solutions positives de la congruence $a^x\equiv 1(\mathrm{mod}n)$ sont exactement les multiples de ${\text{ord}}_n(a)$.
3. $a^k\equiv 1(\mathrm{mod}n)⟺{\text{ord}}_n(a)\mid k$. En particulier, ${\text{ord}}_n(a)\mid \varphi (n)$.

Remarque : Lorsqu'on veut chercher l'ordre d'un entier modulo $n$ à la main : il suffit de tester les diviseurs de $\varphi (n)$.

Exemple

Déterminer les ordres de $2$ modulo $17$, et de $7$ modulo $10$.

Si $h={\text{ord}}_{17}(2)$, alors $h\mid \varphi (17)=16$, d'où $h\in \{1,2,4,8,16\}$. Il est évident que $h\ne 1,2$, de plus $2^4\equiv -1(\mathrm{mod}17)$, alors $h\ne 4$. D'autre part, $2^8=(2^4{)}^2\equiv (-1{)}^2\equiv 1(\mathrm{mod}17)$, donc $h=8$.

Si $h={\text{ord}}_{10}(7)$, alors $h\mid \varphi (10)=4$, d'où $h\in \{1,2,4\}$. Clairement, $h\ne 1$. Cependant, puisque $7^2\equiv -1(\mathrm{mod}10)$, on a aussi $h\ne 2$. En conclusion, $h=4$.

Exemple

Déterminer ${\text{ord}}_n(a)$ dans les cas suivants :

1. $a=2$ et $n\in \{7,11,15\}$.
2. $a=5$ et $n\in \{7,11,23\}$.

On note, dans tous les cas, $d={\text{ord}}_n(a)$, et on utilise le fait que $d\mid \varphi (n)$.

① Si $n=7$ alors $\varphi (7)=6$ et $d\mid 6$. En calculant avec les diviseurs de $6$ on trouve que $d=3$ car $2^3\equiv 1(\mathrm{mod}7)$. Si $n=11$ alors $d\mid 10$, en vérifiant avec les différents diviseurs de $10$ on trouve $d=10$ car $2^{10}\equiv 1(\mathrm{mod}11)$. Si $n=15$ on a $d\mid 8$, on trouve $d=4$ car $2^4\equiv 1(\mathrm{mod}15)$ et $2^2\not\equiv 1(\mathrm{mod}15)$.

② Pour $n=7$ on a $d\mid 6$, comme $7\nmid 5^2-1$ et $7\nmid 5^3-1$ on déduit que $d=6$. Pour $n=11$ on a $d\mid 10$ et $11\nmid 5^2-1$. Ensuite, $5^5\equiv 25\cdot 125\equiv 3\cdot 4\equiv 1(\mathrm{mod}11)$, d'où $d=5$. Finalement, pour $n=23$ on a $d\mid 22$ et $23\nmid 5^2-1$. De plus, $5^{11}\equiv 5\cdot 25^5\equiv 5\cdot 25\equiv 5\cdot 9\equiv -1(\mathrm{mod}23)$, donc $d=22$.

Exemple

Soit $n>1$ un entier naturel. Déterminer ${\text{ord}}_{2^n}(5)$.

Soit $d={\text{ord}}_{2^n}(5)$, alors $d\mid \varphi (2^n)=2^{n-1}$, d'où $d=2^k$ pour un certain $0\le k<n$. Donc on doit trouver le plus petit $k\ge 0$ pour lequel $2^n\mid 5^{2^k}-1$, i.e., tel que $v_2(5^{2^k}-1)\ge 1$. En utilisant la factorisation :

$$5^{2^k}-1=(5-1)(5+1)(5^2+1)\cdots (5^{2^{k-1}}+1)$$

on obtient $v_2(5^{2^k}-1)=k+2$. Donc l'inégalité $v_2(5^{2^k}-1)\ge n$ est équivalente à $k\ge n-2$ et par suite $d=2^{n-2}$.

Exemple

Si $p$ est un nombre premier impair, montrer que tous les facteurs premiers de $2^p-1$ sont de la forme $2kp+1$ pour un certain $k\in {\mathbb{N}}^{\ast }$.

Si $q$ est un facteur premier de $2^p-1$, alors $q$ est impair et $2^p\equiv 1(\mathrm{mod}q)$. Donc ${\text{ord}}_q(2)\mid p$, et alors ${\text{ord}}_q(2)\in \{1,p\}$. Or, si ${\text{ord}}_q(2)=1$, alors $q=1$, absurde. Donc, ${\text{ord}}_q(2)=p$. D'autre part, d'après le théorème de Fermat on sait que $2^{q-1}\equiv 1(\mathrm{mod}q)$, ainsi $p={\text{ord}}_q(2)\mid (q-1)$. Or comme $q$ est impair, il doit exister $k\in {\mathbb{N}}^{\ast }$ tel que $q-1=2kp$.

Proposition

Soient $a$ et $n$ des entiers premiers entre eux avec $n>1$.

1. ${\text{ord}}_n(a)={\text{ord}}_n(a+n)$.
2. Si $m>1$ est un entier tel que $m\mid n$, alors ${\text{ord}}_m(a)\mid {\text{ord}}_n(a)$.
3. Si ${\text{ord}}_n(a)=h$ et $k\in {\mathbb{N}}^{\ast }$, alors ${\text{ord}}_n(a^k)=\frac{h}{\gcd (h,k)}$.
4. Si $k\in {\mathbb{N}}^{\ast }$, alors ${\text{ord}}_n(a^k)={\text{ord}}_n(a)⟺\gcd ({\text{ord}}_n(a),k)=1$.
5. Si ${\text{ord}}_n(a)=h$, alors l'ensemble $\{a,a^2,\cdots ,a^h\}$ possède exactement $\varphi (h)$ éléments d'ordre $h$ modulo $n$.

Preuve

① Comme $a\equiv a+n(\mathrm{mod}n)$ alors $a^k\equiv (a+n{)}^k(\mathrm{mod}n)$ pour tout $k\in {\mathbb{N}}^{\ast }$. En particulier, $a^k\equiv 1(\mathrm{mod}n)$ si, et seulement si, $(a+n{)}^k\equiv 1(\mathrm{mod}n)$, et donc $a$ et $a+n$ ont le même ordre modulo $n$.

② Comme $m\mid n$, alors si $a^k\equiv 1(\mathrm{mod}n)$ on a : $a^k\equiv 1(\mathrm{mod}m)$. En particulier, puisque $a^k\equiv 1(\mathrm{mod}n)$ où $k={\text{ord}}_n(a)$, on a : $a^{{\text{ord}}_n(a)}\equiv 1(\mathrm{mod}m)$. D'où ${\text{ord}}_m(a)\mid {\text{ord}}_n(a)$.

③ Soit $d=\gcd (h,k)$, alors :

$$(a^k{)}^j\equiv 1(\mathrm{mod}n)⟺a^{kj}\equiv 1(\mathrm{mod}n)⟺h\mid kj⟺\frac{h}{d}\mid \frac{k}{d}\cdot j⟺\frac{h}{d}\mid j,$$

où on a utilisé le fait que $\gcd (\frac{h}{d},\frac{k}{d})=1$. On obtient donc que :

$${\text{ord}}_n(a^k)=\frac{h}{d}=\frac{h}{\gcd (h,k)}.$$

④ Découle immédiatement de (3) ci-dessus.

⑤ D'après (4) ci-dessus, le nombre d'exposants $1\le k\le h$ tels que $a^k$ a pour ordre $h$ modulo $n$ est égal au nombre d'exposants $1\le k\le h$ qui sont premiers avec $h$. C'est donc égal à $\varphi (h)$.

Corollaire

1. ${\text{ord}}_n(a^k)=h⟺\gcd (h,k)=1$.
2. Si $k\mid h$, alors ${\text{ord}}_n(a^k)=\frac{h}{k}$.

Exemple

Montrer que, pour tout $n\in {\mathbb{N}}^{\ast }$, le nombre $2^{3^n}+1$ n'est pas un multiple de $17$.

Supposons, par l'absurde, que $2^{3^n}\equiv -1(\mathrm{mod}17)$, alors $2^{2\cdot 3^n}\equiv 1(\mathrm{mod}17)$. Or $2^{16}\equiv 1(\mathrm{mod}17)$, donc ${\text{ord}}_{17}(2)\in \{1,2\}$, une contradiction.

Exemple

Soient $a$ et $n$ des entiers premiers entre eux avec $n>2$. Montrer que s'il existe un entier naturel $k$ tel que $a^k\equiv -1(\mathrm{mod}n)$, alors ${\text{ord}}_n(a)$ est pair.

Si $m={\text{ord}}_n(a)$, alors $m\mid 2k$, et d'après le théorème d'Euler, $m\mid \varphi (n)$. Donc, $m\mid \gcd (2k,\varphi (n))=2d$, où $d=\gcd (k,\varphi (n)/2)$ (rappelons que $n>2⟹\varphi (n)$ pair). Si $m\mid d$, alors $m\mid k$, contradiction. Par suite $m=2d^{\prime }$ pour un certain diviseur $d^{\prime }$ de $d$, et donc $m$ est pair.

Exemple

Soient $p$ et $q$ des nombres premiers tels que $p^2\mid 2^q-1$. Montrer que $2^{p-1}\equiv 1(\mathrm{mod}{p}^2)$.

Soit $d={\text{ord}}_{p^2}(2)$, alors $d\mid \varphi (p^2)=p(p-1)$, et l'hypothèse implique que $d\mid q$. Il est clair que $d\ne 1$, donc nécessairement $d=q$ et par suite $q\mid p(p-1)$. Si $q=p$, on obtient $p\mid 2^p-1$, impossible d'après le théorème de Fermat. Donc $q\mid p-1$, et alors $p^2\mid 2^q-1\mid 2^{p-1}-1$, ce qui termine la preuve.

Exemple (Kvant)

Soit $n\in {\mathbb{N}}^{\ast }$ tel que $2^{2^n}+2^n+1$ soit un nombre premier. Montrer que ce nombre premier est un diviseur de $2^{2^{n+1}}+1$.

Soit $p=2^{2^n}+2^n+1$ et notons que $p\mid 2^{3^n}-1$. Pour montrer que $p\mid 2^{2^{n+1}}-1$ il suffit de montrer que $3n\mid 2^n+1$. Soit $d={\text{ord}}_p(2)$, puisque $2^{3^n}\equiv 1(\mathrm{mod}p)$ on a : $d\mid 3n$. Ensuite, on a $d>2^n>\frac{3n}{2}$ puisque $2^d\equiv 1(\mathrm{mod}p)$ (d'où $2^d>p>2^{2^n}$), qui avec $d\mid 3n$ impliquent $d=3n$. Comme $d\mid p-1$ on conclut que $3n\mid p-1=2^n(2^n+1)$. Finalement, notons que $n$ est impair (si $n$ est pair alors $p>3$ et $p\equiv 0(\mathrm{mod}3)$, une contradiction) d'où $\gcd (3n,2^n)=1$ et ainsi $3n\mid 2^n+1$.

Proposition

Soient $a$ et $n$ deux entiers premiers entre eux, avec $n>1$. Si $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$ est la décomposition primaire de $n$, alors :

$${\text{ord}}_n(a)=\text{ppcm}\left({\text{ord}}_{p_1^{{\alpha }_1}}(a),\cdots ,{\text{ord}}_{p_k^{{\alpha }_k}}(a)\right).$$

Proposition

Soient $p$ un nombre premier, $\alpha \in {\mathbb{N}}^{\ast }$ un entier, et $a>1$ un entier tel que $\gcd (a,p)=1$. Soit $d={\text{ord}}_p(a)$ et posons $v=v_p(a^d-1)\ge 1$.

1. Supposons que $p>2$. Si $v\ge \alpha$ alors ${\text{ord}}_{p^{\alpha }}(a)=d$, sinon : ${\text{ord}}_{p^{\alpha }}(a)=d\cdot p^{\alpha -v}$. En particulier, si $v_p(a^{{\text{ord}}_p(a)}-1)=1$, alors : ${\text{ord}}_{p^{\alpha }}(a)={\text{ord}}_p(a)\cdot p^{\alpha -1}$.
2. Supposons que $p=2$ et $\alpha >1$. Si $a\equiv 1(\mathrm{mod}{2}^{\alpha })$ alors ${\text{ord}}_{2^{\alpha }}(a)=1$ et si $a\equiv -1(\mathrm{mod}{2}^{\alpha })$ alors ${\text{ord}}_{2^{\alpha }}(a)=2$. Dans tous les cas : $${\text{ord}}_{2^{\alpha }}(a)=2^{\alpha -v_2\left(\frac{a^2-1}{2}\right)}.$$

Théorème

1. Soient $p$ un nombre premier impair, $q\ne \pm 1$, et $p\nmid a$. Soit $r$ l'ordre de $a$ modulo $p$, et $p^{k_0}$ la plus grande puissance de $p$ divisant $a^r-1$, i.e., $p^{k_0}\Vert (a^r-1)$. Si $r_k$ est l'ordre de $a$ modulo $p^k$, alors : $$r_k=\{\begin{array}{ll}r& \text{si }k=1,\dots ,k_0,\\ r{p}^{k-k_0}& \text{si }k>k_0.\end{array}$$
2. Supposons que $a$ est impair, $a\equiv 1(\mathrm{mod}4)$, $a\ne 1$, $k_0$ vérifie $2^{k_0}\Vert (a-1)$. Si $l_k$ est l'ordre de $a$ modulo $2^k$, alors : $$l_k=\{\begin{array}{ll}1& \text{si }k=1,\dots ,k_0,\\ 2^{k-k_0}& \text{si }k>k_0.\end{array}$$
3. Supposons que $a$ est impair, $a\equiv -1(\mathrm{mod}4)$, $a\ne -1$, $k_0$ vérifie $2^{k_0}\Vert (a+1)$. Si $l_k$ est l'ordre de $a$ modulo $2^k$ alors : $$l_k=\{\begin{array}{ll}1& \text{si }k=1,\\ 2& \text{si }k=2,\dots ,k_0+1,\\ 2^{k-k_0}& \text{si }k>k_0+1.\end{array}$$

7.2 Exemples

Exemple

Soit $n>1$ un entier naturel. Montrer que si $n\mid (2^n+1)$ alors $3\mid n$.

Il est clair que $n$ est impair. Soit $p$ le plus petit diviseur premier de $n$, on se propose de montrer que $p=3$, ce qui donnera $3\mid n$. Soit $r$ l'ordre de $2$ modulo $p$. Comme $2^n\equiv -1(\mathrm{mod}n)$ alors :

$$2^{2n}\equiv 1(\mathrm{mod}p).(1)$$

Puisque $p\ge 3$, alors par le théorème de Fermat, on a :

$$2^{p-1}\equiv 1(\mathrm{mod}p).(2)$$

Les relations (1) et (2), ainsi que les propriétés de l'ordre, impliquent que $r\mid 2n$ et $r\mid (p-1)$, d'où $r\mid \gcd (2n,p-1)$. Il est facile de montrer que $\gcd (2n,p-1)=2$. En effet, de $2\nmid n$ on obtient $2\mid \gcd (2n,p-1)$, et $2^2\nmid \gcd (2n,p-1)$. D'autre part, s'il existe un nombre premier impair $q$ tel que $q\mid \gcd (2n,p-1)$, alors $q\mid (p-1)$ et $q\mid n$, or cette dernière relation montre que $q<p$, en contradiction $p$ est le plus petit diviseur premier de $n$. Ainsi, $\gcd (2n,p-1)=2$, et $r=2,p=3$.

Exemple

Soit $n>1$ un entier naturel. Montrer que : $n\nmid (2^n-1)$.

Supposons, par l'absurde, qu'il existe un entier $n>1$ tel que $n\mid (2^n-1)$. Pour tout diviseur premier $p$ de $n$, on a : $p\ge 3$. Supposons que l'ordre de $2$ modulo $p$ est $r$, alors clairement $r>1$. De la relation $2^n\equiv 1(\mathrm{mod}n)$ on déduit $2^n\equiv 1(\mathrm{mod}p)$. D'après le théorème de Fermat on a : $2^{p-1}\equiv 1(\mathrm{mod}p)$. Donc, $r\mid n$ et $r\mid (p-1)$. Par suite $r\mid \gcd (n,p-1)$. En particulier, on prend $p$ le plus petit diviseur premier de $n$, alors $\gcd (n,p-1)=1$. En effet, s'il existe un nombre premier $q$ tel que $q\mid \gcd (n,p-1)$, alors $q\mid (p-1)$ et $q\mid n$. Or cette dernière relation entraîne que $q<p$, en contradiction avec le choix de $p$. Donc, $\gcd (n,p-1)=1$. D'où, $r=1$, une contradiction.

Exemple

Soit $n>1$ un entier impair. Montrer que, pour tout $m\in \mathbb{N}$, on a : $n\nmid \left(m^{n-1}+1\right)$.

Supposons, par l'absurde, qu'il existe $n>1$ impair tel que $n\mid \left(m^{n-1}+1\right)$, alors $\gcd (m,n)=1$. Soit $p$ un diviseur premier quelconque de $n$, et $r$ l'ordre de $m$ modulo $p$ (notons que $p\nmid m$). Posons $n-1=2^{k}t$, $k\ge 1$, $2\nmid t$, alors on a :

$$m^{2^{k}t}\equiv -1(\mathrm{mod}p).(1)$$

Par suite $m^{2^{k+1}t}\equiv 1(\mathrm{mod}p)$, d'où $r\mid 2^{k+1}t$. L'étape cruciale dans la résolution de ce problème est de montrer que $2^{k+1}\mid r$. Supposons que ce n'est pas le cas, alors comme $m^r\equiv 1(\mathrm{mod}p)$ on obtient $m^{2^{k}t}\equiv 1(\mathrm{mod}p)$, et grâce à (1) on déduit que $p=2$, une contradiction. Par conséquent $2^{k+1}\mid r$. La relation $\gcd (p,m)=1$ implique que $m^{p-1}\equiv 1(\mathrm{mod}p)$, d'où $r\mid (p-1)$, donc $2^{k+1}\mid (p-1)$, i.e., $p\equiv 1(\mathrm{mod}{2}^{k+1})$. Comme $p$ est un diviseur quelconque de $n$, on peut factoriser $n$ et obtenir $n\equiv 1(\mathrm{mod}{2}^{k+1})$, c'est-à-dire $2^{k+1}\mid (n-1)$. Mais ceci est en contradiction avec $2^k$ la plus grande puissance de $2$ divisant $(n-1)$.

Exemple

Soit $p$ un nombre premier impair. Montrer que tout diviseur strictement positif de $\frac{p^{2p}+1}{p^2+1}$ est congru à $1$ modulo $4p$.

Il suffit de montrer que tout diviseur premier de $\frac{p^{2p}+1}{p^2+1}$ vérifie $q\equiv 1(\mathrm{mod}4p)$. Notons, tout d'abord, que :

$$\frac{p^{2p}+1}{p^2+1}=p^{p-1}-p^{2(p-2)}+\cdots -p^2+1.(1)$$

Donc $q\ne p$. Soit $r$ l'ordre de $p$ modulo $q$. Puisque :

$$p^{2p}\equiv -1(\mathrm{mod}q),(2)$$

alors $p^{4p}\equiv 1(\mathrm{mod}q)$, par suite $r\mid 4p$. Donc : $r\in \{1,2,4,p,2p,4p\}$.

◇ Si $r\in \{1,2,p,2p\}$, alors $p^{2p}\equiv 1(\mathrm{mod}q)$, et avec (2) on déduit que $q=2$, ceci est impossible.

◇ Si $r=4$, alors $q$ est premier, ce qui implique que $q\mid (p^2-1)$ ou $q\mid (p^2+1)$. Le premier cas est impossible. Si le second cas est vrai, i.e., $p^2\equiv -1(\mathrm{mod}q)$, on considère (1) modulo $q$. Il est clair que le membre de gauche est $\equiv 0(\mathrm{mod}q)$, mais le membre de droite est $\equiv (-1{)}^{p-1}-(-1{)}^{p-2}+\cdots -(-1)+1\equiv p(\mathrm{mod}q)$. Donc $p=q$, ce qui est impossible. Ainsi, $r\ne 4$.

Donc $r=4p$. Finalement, comme $\gcd (p,q)=1$, alors d'après le théorème de Fermat $p^{q-1}\equiv 1(\mathrm{mod}q)$. D'où $r\mid (q-1)$, i.e., $4p\mid (q-1)$, donc $q\equiv 1(\mathrm{mod}4p)$.

Exemple

Soient $a$ et $n$ des entiers tels qu'aucun d'eux n'est égal à $\pm 1$, et $\gcd (a,n)=1$. Montrer qu'il y a au plus un nombre fini de $k$ tels que : $n^k\mid (a^k-1)$.

Puisque $n\ne \pm 1$, alors il admet des diviseurs premiers. On suppose, tout d'abord, que $n$ admet un diviseur premier impair $p$, alors $p\nmid a$. Soit $r$ l'ordre de $a$ modulo $p$. Comme $a\ne \pm 1$, il existe $k_0\in {\mathbb{N}}^{\ast }$ tel que $p^{k_0}\Vert (a^r-1)$ (c-à-d $p^{k_0}$ est la plus grande puissance de $p$ divisant $a^r-1$). S'il y a une infinité de tels $k$ vérifiant $n^k\mid (a^k-1)$, alors il y a une infinité de $k>k_0$ tels que :

$$a^k\equiv 1(\mathrm{mod}{p}^k).(1)$$

D'après le théorème vu en début de ce chapitre, l'ordre de $a$ modulo $p^k$ est $r{p}^{k-k_0}$. Donc par (1) on a : $r{p}^{k-k_0}\mid k$, d'où $k\ge r{p}^{k-k_0}\ge 3^{k-k_0}$, et le nombre de tels $k$ est clairement fini, une contradiction. Si $n$ n'admet pas de diviseurs premiers impairs, alors $n$ est une puissance de $2$. Notons d'abord que si $k$ impair vérifie $n^k\mid (a^k-1)$, alors :

$$a^k-1=(a-1)\left(a^{k-1}+\cdots +a+1\right)(2)$$

est divisible par $2^k$. Or le second diviseur dans (2) est la somme d'un nombre impair d'entiers impairs, d'où $2^k\mid (a-1)$. Comme $a\ne 1$, il existe au plus un nombre fini de tels $k$. Supposons qu'il y a un nombre infini d'entiers pairs $k=2l$ tels que $n^k\mid (a^k-1)$, alors :

$${\left(a^2\right)}^l\equiv 1(\mathrm{mod}{2}^l).(3)$$

Soit $k_0$ vérifiant $2^{k_0}\Vert (a^2-1)$, alors $k_0\ge 3$. D'après le théorème vu en début de chapitre, lorsque $l>k_0$ l'ordre de $a^2$ modulo $2^l$ est $2^{l-k_0}$. Donc si $l>k_0$, par (3) on a : $2^{l-k_0}\mid l$, d'où $l\ge 2^{l-k_0}$. Mais il y a au plus un nombre fini de tels $l$, une contradiction.

Exemple

Montrer que si $n\in {\mathbb{N}}^{\ast }$ alors : ${\text{ord}}_{5^n}(2)=4\cdot 5^{n-1}$.

On a clairement ${\text{ord}}_5(2)=4$ et $v_5(2^4-1)=1$. En utilisant la partie (1) de la proposition précédente on obtient ${\text{ord}}_{5^n}(2)=4\cdot 5^{n-1}$.