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.

1.2 Congruences

Définition

Soient $n\in {\mathbb{N}}^{\ast }$, $(a,b)\in {\mathbb{Z}}^2$. On dit que $a$ est congru à $b$ modulo $n$, et on note $a\equiv b(\mathrm{mod}n)$ si et seulement si $n$ divise $b-a$. Ainsi : $$a\equiv b(\mathrm{mod}n)\iff n|(b-a).$$

Exemples : $22\equiv 14(\mathrm{mod}4)$ ; $13\not\equiv 8(\mathrm{mod}4)$.

Proposition

Pour tout $n\in {\mathbb{N}}^{\ast }$, la relation $\equiv (\mathrm{mod}n)$ est une relation d'équivalence dans $\mathbb{Z}$. Pour tout $n\in {\mathbb{N}}^{\ast }$, on note $\mathbb{Z}/n\mathbb{Z}$ au lieu de $\mathbb{Z}/\equiv (\mathrm{mod}n)$.

☐ Pour tout $x\in \mathbb{Z}$, on note $\overline{x}$ la classe de $x$ dans $\mathbb{Z}/n\mathbb{Z}$ : $$\overline{x}=\{y\in \mathbb{Z}:x\equiv y(\mathrm{mod}n)\}=\{x+kn,k\in \mathbb{Z}\}.$$

Proposition

Soit $n\in {\mathbb{N}}^{\ast }$. On a, pour tout $(a,b,c,d)\in {\mathbb{Z}}^4$ : $$\begin{cases} a \equiv b \pmod{n} \\ c \equiv d \pmod{n} \end{cases} \Rightarrow \begin{cases} a + c \equiv b + d \pmod{n} \\ ac \equiv bd \pmod{n} \end{cases}$$

Preuve

Supposons $a\equiv b(\mathrm{mod}n)$ et $c\equiv d(\mathrm{mod}n)$, alors il existe $(\lambda ,\mu )\in {\mathbb{Z}}^2$ tel que $b-a=\lambda n$ et $d-c=\mu n$.
➀ $(b+d)-(a+c)=(b-a)+(d-c)=(\lambda +\mu )n$ et $\lambda +\mu \in \mathbb{Z}$, donc $a+c\equiv b+d(\mathrm{mod}n)$.
➁ $bd-ac=(a+\lambda n)(c+\mu n)-ac=(\lambda c+a\mu +\lambda \mu n)n$ et $\lambda c+a\mu +\lambda \mu n\in \mathbb{Z}$, donc $ac\equiv bd(\mathrm{mod}n)$.

Corollaire

$$\forall (a,b)\in {\mathbb{Z}}^2,\forall k\in {\mathbb{N}}^{\ast },a\equiv b(\mathrm{mod}n)\Rightarrow a^k\equiv b^k(\mathrm{mod}n).$$

Proposition

$(\mathbb{Z}/n\mathbb{Z},+,\cdot )$ est un anneau commutatif.

Exemple

Pour tout entier naturel $n$ : $2^{3n}-1$ est un multiple de $7$.
En effet, $2^3=1+7\equiv 1(\mathrm{mod}7)$, donc $2^{3n}\equiv 1(\mathrm{mod}7)$, et par suite $2^{3n}-1\equiv 0(\mathrm{mod}7)$.
Plus généralement, si $a\in \mathbb{N}$ divise $b\in \mathbb{N}$, alors $2^a-1$ divise $2^b-1$. Dans cet exemple on a pris $a=3$ et $b=3n$.

Exemple (Généralisation)

Pour tout entier $n$, $10^{9n+2}+10^{6n+1}+1$ est un multiple de $111$.
En effet, $10^3=1+9\times 111\equiv 1(\mathrm{mod}111)$, d'où : $$10^{9n+2}={\left(10^3\right)}^{3n}\cdot 10^2\equiv 100(\mathrm{mod}111),10^{6n+1}={\left(10^3\right)}^{2n}\cdot 10\equiv 10(\mathrm{mod}111).$$ En conclusion, $10^{9n+2}+10^{6n+1}+1\equiv 100+10+1\equiv 0(\mathrm{mod}111)$.

Proposition (critères usuels de divisibilité)

Soit $n=\sum _{k=0}^r{a}_{k}10^k$ avec, pour tout $k\in [[0,r]]$, $a_k\in [[0,9]]$.

• $n$ est un multiple de $2$ si, et seulement si, $a_0$ est un multiple de $2$.
• $n$ est un multiple de $3$ si, et seulement si, la somme des chiffres $a_0+a_1+\cdots +a_r$ est un multiple de $3$.
• $n$ est un multiple de $4$ si, et seulement si, $10a_1+a_0$ est un multiple de $4$.
• $n$ est un multiple de $5$ si, et seulement si, $a_0$ est un multiple de $5$.
• $n$ est un multiple de $9$ si, et seulement si, la somme des chiffres $a_0+a_1+\cdots +a_r$ est un multiple de $9$.
• $n$ est un multiple de $11$ si, et seulement si, la somme alternée des chiffres $\sum _{k=0}^r{a}_k(-1{)}^k$ est un multiple de $11$.

Preuve

Il suffit de remarquer que $10\equiv 0(\mathrm{mod}2)$, $10\equiv 1(\mathrm{mod}3)$, $100\equiv 0(\mathrm{mod}4)$, $10\equiv 0(\mathrm{mod}5)$, $10\equiv 1(\mathrm{mod}9)$ et $10\equiv -1(\mathrm{mod}11)$ pour obtenir le reste de $10^k$ modulo le diviseur concerné. En effet :
☐ $n\equiv a_0(\mathrm{mod}2)$ car $10^k\equiv 0(\mathrm{mod}2)$ pour tout $k\ge 1$,
☐ $n\equiv \sum _{k=0}^r{a}_k(\mathrm{mod}3)$ car $10^k\equiv 1(\mathrm{mod}3)$ pour tout $k$,
☐ $n\equiv 10a_1+a_0(\mathrm{mod}4)$ car $10^k\equiv 0(\mathrm{mod}4)$ pour tout $k\ge 2$,
☐ $n\equiv a_0(\mathrm{mod}5)$ car $10^k\equiv 0(\mathrm{mod}5)$ pour tout $k\ge 1$,
☐ $n\equiv \sum _{k=0}^r{a}_k(\mathrm{mod}9)$ car $10^k\equiv 1(\mathrm{mod}9)$ pour tout $k$,
☐ $n\equiv \sum _{k=0}^r{a}_k(-1{)}^k(\mathrm{mod}11)$ car $10^k\equiv (-1{)}^k(\mathrm{mod}11)$ pour tout $k$.

Proposition (formule de Bernoulli)

1. Soient $(a,b)\in {\mathbb{Z}}^2$ et $n\in {\mathbb{N}}^{\ast }$, alors : $a-b\mid a^n-b^n$.
2. Soient $(a,b)\in {\mathbb{Z}}^2$ et $n$ un entier naturel impair, alors : $a+b\mid a^n+b^n$.

➀ Cela découle immédiatement de la formule : $$a^n-b^n=(a-b)\left(a^{n-1}+a^{n-2}b+\cdots +a{b}^{n-2}+b^{n-1}\right).$$

➁ Pour $n$ impair, on peut écrire $(-b{)}^n=-b^n$, la formule précédente peut être réutilisée de la manière suivante : $$a^n+b^n=a^n-(-b{)}^n=(a-(-b))\left(a^{n-1}+a^{n-2}(-b)+\cdots +a(-b{)}^{n-2}+(-b{)}^{n-1}\right)$$ c'est-à-dire $a^n+b^n=(a+b)\left(a^{n-1}-a^{n-2}b-\cdots -a{b}^{n-2}+b^{n-1}\right)$, d'où le résultat.

Corollaire

Soient $n\in {\mathbb{N}}^{\ast }$, et $d$ un diviseur (positif) de $n$. Alors, pour tout $a\ge 1$ on a : $a^d-1\mid a^n-1$.
En effet, $d$ est un diviseur de $n\ne 0$ donc il existe $k\in {\mathbb{N}}^{\ast }$ tel que $n=kd$. Par suite : $$a^n-1={\left(a^d\right)}^k-1=(a^d-1)\left({\left(a^d\right)}^{k-1}+{\left(a^d\right)}^{k-2}+\cdots +1\right),$$ donc on a bien $a^d-1\mid a^n-1$.

Exemple

Montrer que $2^{100}-1$ est divisible par $3$ et par $31$.
On applique le corollaire ci-dessus. $d=2$ est un diviseur de $n=100$ donc $2^2-1=3$ divise $2^{100}-1$. De même, $5$ est un diviseur de $100$, donc $2^5-1=31$ divise $2^{100}-1$.

Théorème 1

Soit $n$ un entier non nul. Il existe une unique paire $(a,b)$ d'entiers, avec $a\ge 0$ et $b$ impair, telle que : $n=2^a\cdot b$.

Démonstration

On commence par montrer l'unicité. Supposons que $2^{a}b=2^{c}d$ avec $a,c\ge 0$ et $b,d$ impairs. Supposons, par l'absurde, que $a\ne c$. On peut supposer, sans perte de généralité, que $a<c$, alors $b=2^{c-a}d$ est pair, contradiction. Ainsi, $a=c$ et $b=d$.
Pour montrer l'existence on considère l'ensemble des puissances de $2$ qui divisent $n$. Cet ensemble est fini car si $2^a\mid n$ alors $a<2^a\le |n|$. Il y a donc un plus grand élément $a$ tel que $2^a\mid n$. On écrit $n=2^a\cdot b$ pour un entier $b$. Si $b$ est pair, alors $b=2c$ pour un certain entier $c$ et alors $2^{a+1}\mid n$, en contradiction avec la maximalité de $a$. Donc $b$ est impair, ce qui termine la preuve.

☐ Si $a$ et $b$ sont des entiers tels que $ab$ est une puissance de $2$, i.e., $ab=2^n$ pour un certain $n\in \mathbb{N}$, alors $|a|$ et $|b|$ (mais non nécessairement $a$ et $b$) sont des puissances de $2$.
☐ Si $n=2m$ est pair, et $d$ est un entier impair divisant $n$, alors $d$ divise $m$ (découle de l'unicité dans le théorème ci-dessus).

Théorème 2

Si $a$ est un entier impair, alors pour tout $n\in \mathbb{N}$ on a : $2^{n+2}\mid a^{2^n}-1$.

Démonstration

On a : $a^{2^n}-1=(a-1)(a+1)(a^2+1)(a^4+1)\cdots (a^{2^{n-1}}+1)$. Comme $a$ est impair, $(a-1)(a+1)=a^2-1$ est un multiple de $8$, et chacun de $a^2+1,a^4+1,\dots ,a^{2^{n-1}}+1$ est un multiple de $2$, donc $a^{2^n}-1$ est un multiple de $2^{3+(n-1)}=2^{n+2}$.

Les deux théorèmes ci-haut ont beaucoup d'applications, on en donne quelques exemples :

Exemple

Soit $n>1$ un entier. Montrer que $n$ est impair si, et seulement si, $n\mid 1^n+2^n+\cdots +(n-1{)}^n$.
Posons, pour simplifier, $a_n=1^n+2^n+\cdots +(n-1{)}^n$.
⋄ Si $n$ est impair, alors $k^n+(n-k{)}^n$ est un multiple de $n$ pour $1\le k\le n-1$, par suite $2a_n$ est un multiple de $n$ et alors $n\mid a_n$.
⋄ Supposons que $n$ est pair et écrivons $n=2^{a}m$ avec $a\ge 1$ et $m$ impair. Si $k$ est impair, alors $k^n=(k^{2^a}{)}^m\equiv 1(\mathrm{mod}{2}^a)$, tandis que si $k$ est pair, alors $k^n\equiv 0(\mathrm{mod}{2}^a)$. On déduit que : $a_n\equiv 2^{a-1}m(\mathrm{mod}{2}^a)$, et alors $2^a$ ne peut pas diviser $a_n$.

Exemple

Montrer que si $n>1$ alors $s=1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}$ n'est pas un entier.
Soient $a$ le produit de tous les entiers impairs plus petits ou égaux à $n$, et $k$ le plus grand entier tel que $2^k\le n$. On affirme que $2^{k-1}as$ n'est pas un entier. Si $1\le m\le n$ avec $m\ne 2^k$, alors $m$ peut s'écrire sous la forme $2^{t}u$ avec $0\le t\le k-1$ et $1\le u\le n$ est un entier impair. Donc, $m\mid 2^{k-1}a$, d'où $2^{k-1}a\cdot \frac{1}{m}$ est un entier. Par conséquent $2^{k-1}as=N+\frac{a}{2}$ pour un certain entier $N$. Or $a$ est impair, d'où $\frac{a}{2}$ n'est pas un entier. En conclusion, $s$ n'est pas un entier.

Exemple

Existe t-il un polynôme $P(x,y)$, à deux variables, et à coefficients entiers, tel que :
(i) l'équation $f(x,y)=0$ n'admet pas de solutions entières,
(ii) pour tout $n\in {\mathbb{N}}^{\ast }$, il existe des entiers $x,y$ tels que : $n\mid f(x,y)$ ?
La réponse est oui. On montre que $f(x,y)=(2x-1)(3y-1)$ répond à la question. Les solutions de $f(x,y)=0$ sont $\frac{1}{2}$ et $\frac{1}{3}$, donc pas de solutions entières. Maintenant, soit $n\in {\mathbb{N}}^{\ast }$, et écrivons $n=2^{k}m$ avec $k\ge 0$ et $m$ impair. Puisque $3\mid 4^k-1$, alors : $$3\mid 2^{2k+1}+1=2\cdot 4^k+1,$$ donc on peut écrire $2^{2k+1}=3y-1$ pour un certain entier $y$. En prenant $x=\frac{m+1}{2}$ (un entier car $m$ impair), on obtient : $(2x-1)(3y-1)=m\cdot 2^{2k+1}$ un multiple de $n$.

1.3 Exemples

Exemple

Soit $n\in {\mathbb{Z}}^{\ast }$. Montrer que :
⋄ si $n$ est pair, alors $n^2\equiv 0(\mathrm{mod}8)$ ou $n^2\equiv 4(\mathrm{mod}8)$;
⋄ si $n$ est impair, alors $n^2\equiv 1(\mathrm{mod}8)$.
⋄ Si $n=2p$ ($p\in \mathbb{Z}$), alors $n^2=4p^2$, donc $n^2\equiv 0(\mathrm{mod}4)$, d'où $n^2\equiv 0$ ou $4(\mathrm{mod}8)$.
⋄ Si $n=2p+1$ ($p\in \mathbb{Z}$), alors $n^2=4p(p+1)+1$, donc $n^2\equiv 1(\mathrm{mod}8)$ car $p(p+1)$ est pair vu que $p$ ou $p+1$ est pair.

Exemple

Montrer que, pour tout $n\in {\mathbb{N}}^{\ast }$, $\sum _{k=1}^{2n}\frac{(2n)!}{k}$ est un entier divisible par $2n+1$.
On a : $$\sum _{k=1}^{2n}\frac{(2n)!}{k}=\sum _{k=1}^n\frac{(2n)!}{k}+\sum _{k=n+1}^{2n}\frac{(2n)!}{k}=\sum _{k=1}^n\frac{(2n)!}{k}+\sum _{m=1}^n\frac{(2n)!}{2n+1-m}=\sum _{k=1}^n(2n)!\left(\frac{1}{k}+\frac{1}{2n+1-k}\right)$$ $$=(2n+1)\cdot \sum _{k=1}^n\frac{(2n)!}{k(2n+1-k)}.$$ Comme, pour tout $k\in \{1,2,\dots ,n\}$, $k$ et $2n+1-k$ sont distincts et inférieurs à $2n$, le rationnel $\frac{(2n)!}{k(2n+1-k)}$ est un entier.

Exemple

Montrer que : $\forall n\in {\mathbb{N}}^{\ast },40^n\cdot n!\mid (5n)!$
On utilise une récurrence sur $n$. La propriété est immédiate pour $n=1$. Supposons-la vraie pour un $n\in {\mathbb{N}}^{\ast }$. Comme : $$(5(n+1))!=(5n)!\cdot (5n+1)(5n+2)(5n+3)(5n+4)(5n+5)\text{et}40^{n+1}(n+1)!=(40^{n}n!)40(n+1),$$ il suffit alors de prouver que $8\mid (5n+1)(5n+2)(5n+3)(5n+4)$. Parmi les $4$ nombres consécutifs $5n+1,5n+2,5n+3,5n+4$, il y en a $2$ qui sont pairs, et l'un de ces $2$ derniers est multiple de $4$.
Remarque : on peut aussi utiliser le fait que $\left(\genfrac{}{}{0ex}{}{5n+4}{4}\right)\in \mathbb{N}$.

Exemple

Déterminer tous les entiers $n\in \mathbb{N}\setminus \{0,1\}$ tels que $(2n-1)\mid (3n^2-3n+1)(3n^2-3n+2)$.
On se propose de montrer que le seul entier vérifiant cette propriété est $n=3$. Tout d'abord, il est clair que $380$ est divisible par $5$. Réciproquement, en notant $m=2n-1$ et $u_n=(3n^2-3n+1)(3n^2-3n+2)$, alors $u_n=\frac{(3m^2+1)(3m^2+5)}{16}$, par suite : $$(2n-1)\mid u_n\Rightarrow m\mid (3m^2+1)(3m^2+5)\Rightarrow m\mid 5\Rightarrow m\in \{1,5\}\Rightarrow n=3.$$ donc on peut écrire $2^{2k+1}=3y-1$ pour un certain entier $y$. En prenant $x=\frac{m+1}{2}$ (un entier car $m$ impair), on obtient : $(2x-1)(3y-1)=m\cdot 2^{2k+1}$ un multiple de $n$.

Exemple

Soit $n\in \mathbb{N}$ tel que $n\ge 4$. Montrer qu'il existe $k\in \mathbb{N}$ tel que : $n!<k<(n+1)!$ et $n^3\mid k$.
Posons $E_n=\{k\in \mathbb{N}:n!<k<(n+1)!\}$. Pour qu'il existe $k\in E_n$ tel que $n^3\mid k$, il suffit que $E_n$ contienne au moins $n^3$ nombres consécutifs (parmi lesquels il y aura alors un multiple de $n^3$).
Puisque $|E_n|=(n+1)!-n!-1=n\cdot n!-1$, il suffit de montrer que $n\cdot n!\ge n^3+1$ pour tout entier $n\ge 4$. Cela se fait sans grandes difficultés grâce au raisonnement par récurrence.

Exemple

Soit $(a,b,c,d)\in {\mathbb{Z}}^4$ tel que $ad+bc\ne 0$. On suppose que $ad+bc$ divise $a,b,c,d$. Montrer que $ad+bc=\pm 1$.
Posons $m=ad+bc$, alors il existe $(\alpha ,\beta ,\gamma ,\delta )\in {\mathbb{Z}}^4$ tel que $a=m\alpha ,b=m\beta ,c=m\gamma$ et $d=m\delta$. Par suite : $$m=ad+bc=m^2(\alpha \delta +\beta \gamma )\text{d’ouˋ}{m}^2\mid m\text{i.e.}m\in \{-1,0,1\}.$$

Exemple

Montrer que, pour tout $n\in \mathbb{N}$, ${\left(3+\sqrt{5}\right)}^n+{\left(3-\sqrt{5}\right)}^n$ est un entier divisible par $2^n$.
En notant $r_1=\frac{3-\sqrt{5}}{2}$, $r_2=\frac{3+\sqrt{5}}{2}$, et $u_n=r_1^n+r_2^n$, alors $(u_n{)}_{n\ge 0}$ est une suite récurrence linéaire du second ordre à coefficient constants, et on a pour tout $n\in \mathbb{N}$ : $$u_{n+2}-(r_1+r_2)u_{n+1}+r_1{r}_2{u}_n=0\text{c’est-aˋ-dire}{u}_{n+2}=3u_{n+1}-u_n.$$ Comme $u_0=2$ et $u_1=3$, il est alors clair (par récurrence à deux pas sur $n$) que $u_n\in \mathbb{Z}$ pour tout $n\in \mathbb{N}$, et même $u_n\in \mathbb{N}$ pour tout $n\in \mathbb{N}$ puisque $r_1\ge 0$ et $r_2\ge 0$. Ainsi, pour tout $n\in \mathbb{N}$, $${\left(3+\sqrt{5}\right)}^n+{\left(3-\sqrt{5}\right)}^n=2^n{u}_n,$$ donc c'est un entier divisible par $2^n$.

Exemple

Soient $n\in {\mathbb{N}}^{\ast }$ et $1=d_1<d_2<\cdots <d_k=n$ les diviseurs $\ge 1$ de $n$. Montrer que : $(d_1{d}_2\cdots d_k{)}^2=n^k$.
⋄ Si $k$ est impair, $k=2l+1$ avec $l\in \mathbb{N}$, alors : $$n=d_1{d}_{2l+1}=d_2{d}_{2l}=\cdots =d_l{d}_{l+2}=d_{l+1}^2,\text{d’ouˋ}{\left(\prod _{i=1}^k{d}_i\right)}^2=\prod _{i=1}^k{d}_i{d}_{2l+2-i}=n^k.$$ ⋄ Si $k$ est pair, démonstration analogue.

Exemple

Montrer que pour tout $n\in \mathbb{N}\setminus \{0,1\}$, $2^n\mid 5^{2^{n-2}}-1$ et $2^{n+1}\nmid 5^{2^{n-2}}-1$.
Il suffit de remarquer que $5^{2^{n-2}}-1=4\prod _{k=0}^{n-3}\left(5^{2^k}+1\right)$ (si $n\ge 3$), et chacun des facteurs $5^{2^k}+1$ ($k\in \mathbb{N}$) est pair, mais congru à $2$ modulo $4$.

Exemple

Montrer que pour tout $n\in \mathbb{N}$ : $5\mid 2^{2n+1}+3^{2n+1}$.
Dans les questions ne faisant intervenir $n$ qu'en exposant, on peut souvent utiliser des congruences.
À savoir : On a : $2^{2n+1}+3^{2n+1}=4^n\cdot 2+9^n\cdot 3\equiv 4^n(2+3)\equiv 0(\mathrm{mod}5)$.

Exemple

Montrer que pour tout $n\in \mathbb{N}$ : $9\mid 4^n-1-3n$.
Dans les questions mélangeant des exponentielles et des polynômes, une récurrence permettra souvent de conclure.
À savoir : En notant $u_n=4^n-1-3n$, on a $u_0=0$, et si $u_n\equiv 0(\mathrm{mod}9)$, alors : $$u_{n+1}=4^{n+1}-1-3(n+1)=4(u_n+1+3n)-3n-4=4u_n+9n\equiv 0(\mathrm{mod}9).$$

Exemple

Montrer que pour tout $n\in \mathbb{N}$ : $2^{12}\mid 3\cdot 81^{n+1}+(16n-54)9^{n+1}-320n^2-144n+243$.
Notons $u_n=3\cdot 81^{n+1}+(16n-54)9^{n+1}-320n^2-144n+243$. Alors : $$u_n=\left[3\cdot 9^{n+1}+(40n-27)\right]\cdot \left[9^{n+1}+(-8n-9)\right]=64\cdot {\alpha }_n\cdot {\beta }_n$$ où ${\alpha }_n=\frac{27(9^n-1)+40n}{8}=27\sum _{k=0}^{n-1}{9}^k+5n$ et ${\beta }_n=\frac{9(9^n-1)-8n}{8}=9\sum _{k=0}^{n-1}{9}^k-n$.
Puisque $9\equiv 1(\mathrm{mod}8)$, alors : $${\alpha }_n\equiv 27\sum _{k=0}^{n-1}1+5n=32n\equiv 0(\mathrm{mod}8)\text{et}{\beta }_n\equiv 9\sum _{k=0}^{n-1}1-n=8n\equiv 0(\mathrm{mod}8).$$ Ainsi, $8\mid {\alpha }_n$ et $8\mid {\beta }_n$, d'où $2^{12}=64^2\mid u_n$.

Exemple

Soient $a\in \mathbb{Z}$ impair et $n\in \mathbb{N}$ tel que $n\ge 3$. Montrer que $a^{2^{n-2}}\equiv 1(\mathrm{mod}{2}^n)$.
On fait une récurrence sur $n$ (pour $a\in \mathbb{Z}$ impair fixé). Pour $n=3$, $a^{2^{n-2}}=a^2\equiv 1(\mathrm{mod}8)$.
Supposons que $a^{2^{n-2}}\equiv 1(\mathrm{mod}{2}^n)$, il existe $\lambda \in \mathbb{Z}$ tel que $a^{2^{n-2}}=1+\lambda 2^n$. On a alors : $$a^{2^{n-1}}={\left(a^{2^{n-2}}\right)}^2=(1+\lambda 2^n{)}^2=1+\lambda 2^{n+1}+{\lambda }^2{2}^{2n}\equiv 1(\mathrm{mod}{2}^{n+1})\text{car}2n\ge n+1.$$

Exemple

Montrer que pour tout $(a,b,c)\in {\mathbb{Z}}^3$ : $7\mid a^3+b^3+c^3\Rightarrow 7\mid abc$.
Dans $(\mathbb{Z}/7\mathbb{Z},+,\cdot )$ on a :

Soit $(a,b,c)\in {\mathbb{Z}}^3$ tel que $7\nmid abc$, alors $a\ne 0,b\ne 0,c\ne 0$, donc ${\overline{a}}^3,{\overline{b}}^3,{\overline{c}}^3\in \{-1,1{\}}^3$, d'où : $${\overline{a}}^3+{\overline{b}}^3+{\overline{c}}^3\in \{-3,-1,1,3\},$$ et par suite $7\nmid a^3+b^3+c^3$. En conclusion, si $7\mid a^3+b^3+c^3$ alors $7\mid abc$.

Exemple

Trouver tous les $n\in \mathbb{Z}$ tels que : $10\mid n^2+(n+1{)}^2+(n+3{)}^2$.
On a : $n^2+(n+1{)}^2+(n+3{)}^2=3n^2+8n+10\equiv 3n^2-2n(\mathrm{mod}10)$. Or modulo $10$ on a :

En conclusion, $n\equiv 0(\mathrm{mod}10)$ ou $n\equiv 4(\mathrm{mod}10)$.

Exemple

Trouver tous les $n\in \mathbb{N}$ tels que : $21\mid 2^{2n}+2^n+1$.
Comme $2^6=64\equiv 1(\mathrm{mod}21)$, la classe de $2^n$ modulo $21$ dépend de la classe de $n$ modulo $6$ :

En conclusion, $n\equiv 2(\mathrm{mod}6)$ ou $n\equiv 4(\mathrm{mod}6)$.

Exemple

Trouver tous les $n\in \mathbb{N}$ tels que : $7\mid 2^{2^n}+2^n+1$.
Comme $2^3=8\equiv 1(\mathrm{mod}7)$, la classe de $2^n$ modulo $7$ dépend de la classe de $n$ modulo $3$.
D'autre part, puisque $2^2=4\equiv 1(\mathrm{mod}3)$, la classe de $2^n$ modulo $3$ dépend de la classe de $n$ modulo $2$. D'où le tableau :

En conclusion, $n\equiv 1(\mathrm{mod}6)$ ou $n\equiv 2(\mathrm{mod}6)$.