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.

5.1 Définitions. Propriétés

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)⟺n|(b-a).$$

Propriété 1

1. Réflexivité : $a\equiv a(\mathrm{mod}n)$.
2. Symétrie : si $a\equiv b(\mathrm{mod}n)$, alors $b\equiv a(\mathrm{mod}n)$.
3. Transitivité : si $a\equiv b(\mathrm{mod}n)$ et $b\equiv c(\mathrm{mod}n)$, alors $a\equiv c(\mathrm{mod}n)$.

À partir de la définition de la congruence, on voit que tous les nombres dans la progression arithmétique $\{a+kn:k\in \mathbb{Z}\}$ sont congrus à $a$.

La congruence mod $n$ est une relation d'équivalence (propriété 1 ci-dessus) dont les classes d'équivalences sont exactement les différentes progressions arithmétiques de raison $n$.

Définition

Une classe d'équivalence modulo $n$ est appelée une classe de congruence modulo $n$ ou un résidu modulo $n$. L'ensemble de tous les résidus modulo $n$ est noté $\mathbb{Z}/n\mathbb{Z}$. Finalement, un système complet de représentants des classes d'équivalence modulo $n$ est appelé un système complet de résidus modulo $n$.

On utilisera la notation $a(\mathrm{mod}n)$ pour noter la classe d'équivalence de $a$ modulo $n$.

Proposition

Pour tout $n\in \mathbb{N}$, l'ensemble $\{0,1,\cdots ,n-1\}$ est un système complet de résidus modulo $n$, c'est-à-dire $\mathbb{Z}/n\mathbb{Z}=\{0(\mathrm{mod}n),1(\mathrm{mod}n),\cdots ,n-1(\mathrm{mod}n)\}$. En particulier, $|\mathbb{Z}/n\mathbb{Z}|=n$.

À partir du système complet de résidus $\{0,1,\cdots ,n-1\}$, on peut construire d'autres systèmes complets :

Proposition

Soient $n\in \mathbb{N}$ et $a,b\in \mathbb{Z}$. Si $a\wedge n=1$, alors l'ensemble $$\{aj+b:j\in \{0,n-1\}\}$$ est un système complet de résidus.

Un ensemble de $n$ nombres $c_1,c_2,\cdots ,c_n$ est un système complet de résidus modulo $n$ si, et seulement si, n'importe quels deux éléments parmi eux ne sont pas congrus l'un à l'autre modulo $n$.

Corollaire

Soit $n\in {\mathbb{N}}^{\ast }$. Un ensemble de $n$ nombres entiers consécutifs est un système complet de résidus modulo $n$. En particulier, l'ensemble $\mathbb{Z}\cap \left[-\frac{n}{2},\frac{n}{2}\right]$ est un système complet de résidus modulo $n$.

Propriété 2

1. Addition des congruences : si $a\equiv b(\mathrm{mod}n)$ et $c\equiv d(\mathrm{mod}n)$, alors $a\pm c\equiv b\pm d(\mathrm{mod}n)$.
2. Multiplication des congruences : si $a\equiv b(\mathrm{mod}n)$ et $c\equiv d(\mathrm{mod}n)$, alors $ac\equiv bd(\mathrm{mod}n)$.

En appliquant, de façons répétées la propriété 2 on déduit que :

Corollaire

Si $a\equiv b(\mathrm{mod}n)$, $k$ et $c$ des entiers avec $k>0$, alors : $a^{k}c\equiv b^{k}c(\mathrm{mod}n)$.

Attention, on n'a pas en général : $ac\equiv bc(\mathrm{mod}n)\Rightarrow a\equiv b(\mathrm{mod}n)$, par contre on a le résultat :

Propriété 3

Si $ac\equiv bc(\mathrm{mod}n)$ alors $a\equiv b(\mathrm{mod}\frac{n}{n\wedge c})$. Donc, si $c\wedge n=1$, alors $a\equiv b(\mathrm{mod}n)$.

Propriété 4

1. Si $a\equiv b(\mathrm{mod}n)$ et $d|n$, alors $a\equiv b(\mathrm{mod}d)$.
2. Si $a\equiv b(\mathrm{mod}n)$ et $d\ne 0$, alors $da\equiv db(\mathrm{mod}dn)$.
3. Si $a\equiv b(\mathrm{mod}{n}_i)$, $i=1,2,\cdots ,k$, alors $a\equiv b(\mathrm{mod}\text{ppcm}(n_1,n_2,\cdots ,n_k))$. Si $n_1,\cdots ,n_k$ sont 2 à 2 premiers entre eux, alors $a\equiv b(\mathrm{mod}{n}_1{n}_2\cdots n_k)$.

Propriété 5

Soient $a,b$ et $n$ des entiers avec $a\wedge n=1$. Si $c_1,c_2,\cdots ,c_n$ est un système complet de résidus mod $n$, alors $a{c}_1+b,a{c}_2+b,\cdots ,a{c}_n+b$ est aussi un système complet de résidus mod $n$.

Proposition

Soient $a,b$ et $m$ des entiers, et posons $d=a\wedge m$. Si $b$ est un multiple de $d$ il existe une solution de l'équation $ax\equiv b(\mathrm{mod}m)$. Si $x_0$ est une solution, il y a $d$ solutions : $x=x_0+\frac{m}{d}k$ où $k\in \mathbb{Z}$.

Propriété 6

Soient $m$ un entier strictement positif, et $a,b$ deux entiers relativement premiers avec $m$. Alors $$\begin{cases} a^x \equiv b^x \pmod{m} \\ a^y \equiv b^y \pmod{m} \end{cases} \Rightarrow a^{\gcd(x,y)} \equiv b^{\gcd(x,y)} \pmod{m}.$$

Preuve

D'après l'identité de Bézout, il existe deux entiers $u$ et $v$ tels que $\gcd (x,y)=ux-vy$. Alors, on a par hypothèse : $$a^{ux}\equiv b^{ux}(\mathrm{mod}m)\text{ et }{b}^{vy}\equiv a^{vy}(\mathrm{mod}m).$$ D'où $a^{ux}{b}^{vy}\equiv a^{vy}{b}^{ux}(\mathrm{mod}m)$. Comme $\gcd (a,m)=\gcd (b,m)=1$, alors par la propriété 3 on a : $$a^{\gcd (x,y)}\equiv a^{ux-vy}\equiv b^{ux-vy}\equiv b^{\gcd (x,y)}(\mathrm{mod}m).$$

Proposition

1. Les carrés parfaits sont congrus à $0,1(\mathrm{mod}4)$ ; congrus à $0,1,4(\mathrm{mod}8)$ ; congrus à $0,1(\mathrm{mod}3)$ ; congrus à $0,-1,1(\mathrm{mod}5)$ ; congrus à $0,1,4,5,6,9(\mathrm{mod}10)$.
2. Les cubes parfaits sont congrus à $0,-1,1(\mathrm{mod}9)$.
3. Les puissances quatrièmes sont congrues à $0,1(\mathrm{mod}16)$.

5.2 Exemples

Exemple

Déterminer le reste de la division de $17^{2022}$ par $13$.

Comme $17\equiv 4(\mathrm{mod}13)$ et $16\equiv 3(\mathrm{mod}13)$, alors : $$17^{2022}\equiv 4^{2022}=16^{1011}\equiv 3^{1011}(\mathrm{mod}13).$$ Maintenant, en notant que $3^3\equiv 1(\mathrm{mod}13)$ on déduit que : $$3^{1011}=3^{337\cdot 3}={\left(3^3\right)}^{337}\equiv 1^{337}=1(\mathrm{mod}13).$$

Exemple

Soient $a,b,c$ et $d$ des entiers strictement positifs. Montrer que l'entier $a^{4b+d}-a^{4c+d}$ est divisible par $240$.

Puisque $240=2^4\times 3\times 5$, on se propose de montrer que $a^{4b+d}-a^{4c+d}$ est divisible par $3,5$ et $16$.

• On a tout d'abord $3|\left(a^{4b+d}-a^{4c+d}\right)$. En effet, on a : $a^2\equiv 0,1(\mathrm{mod}3)$, et $a^{4b}\equiv a^{4c}\equiv 0,1(\mathrm{mod}3)$, par suite : $$a^{4b+d}-a^{4c+d}=a^d\left(a^{4b}-a^{4c}\right)\equiv 0(\mathrm{mod}3).$$
• Puisque $a^2\equiv 0,\pm 1(\mathrm{mod}5)$, alors $a^4\equiv 0,1(\mathrm{mod}5)$, d'où $a^{4b}\equiv a^{4c}\equiv 0,1(\mathrm{mod}5)$. Par conséquent, $a^{4b+d}-a^{4c+d}\equiv 0(\mathrm{mod}5)$.
• Puisque $a^4\equiv 0,1(\mathrm{mod}16)$, alors $a^{4b}\equiv a^{4c}\equiv 0,1(\mathrm{mod}16)$. Par suite $a^{4b+d}-a^{4c+d}\equiv 0(\mathrm{mod}16)$.

Exemple

Soient $a,b$ et $c$ des entiers tels que $a+b+c=0$. Posons $d=a^{1999}+b^{1999}+c^{1999}$. Montrer que $|d|$ n'est pas un nombre premier.

Notons, tout d'abord, que pour tout entier $u$, les nombres $u^{1999}$ et $u$ sont de même parité, i.e., $u^{1999}\equiv u(\mathrm{mod}2)$. D'où, $d\equiv a+b+c\equiv 0(\mathrm{mod}3)$. Par suite $2|d$. D'autre part, il est facile de vérifier (en distinguant les cas $3|u$ et $3\nmid u$) que $u^3\equiv u(\mathrm{mod}3)$, ce qui implique que : $$u^{1999}\equiv u\cdot u^{1998}\equiv u\cdot u^{666}\equiv u\cdot u^{222}\equiv u^{75}\equiv u^{25}\equiv u^9\equiv u^3\equiv u(\mathrm{mod}3).$$ Par conséquent, $d\equiv a+b+c\equiv 0(\mathrm{mod}3)$. Ainsi, $6|d$, et $d$ n'est donc pas un nombre premier.

Exemple

On suppose que les entiers $x,y$ et $z$ vérifient : $$(x-y)(y-z)(z-x)=x+y+z.(1)$$ Montrer que $x+y+z$ est divisible par $27$.

De la relation (1) on déduira que $x-y\equiv y-z\equiv z-x\equiv 0(\mathrm{mod}3)$ ce qui donnera $27|(x+y+z)$. On fait une preuve par l'absurde.

• Supposons qu'il y a juste deux des nombres $x,y,z$ qui sont congrus modulo $3$, par exemple $x\equiv y(\mathrm{mod}3)$, donc $x\not\equiv z(\mathrm{mod}3)$. Dans ce cas $3|(x-y)$ mais $3\nmid (x+y+z)$. Par suite le membre de gauche de (1) est $\equiv 0(\mathrm{mod}3)$, or le membre de droite de (1) est $\not\equiv 0(\mathrm{mod}3)$, une contradiction.
• Supposons, ensuite, que chaque deux de $x,y$ et $z$ ne sont pas congrus modulo $3$. Dans ce cas, il est facile de vérifier que $3|(x+y+z)$, mais $3\nmid (x-y)(y-z)(z-x)$. Par suite, les restes modulo $3$ des deux membres de (1) ne sont pas égaux, une contradiction. Donc ce cas est aussi impossible.

Exemple

Soit $n>1$ un entier naturel. Montrer que $\underset{n}{\underbrace{11\cdots 1}}$ n'est pas un carré parfait.

Supposons, par l'absurde, qu'il existe un entier $n>1$ et un entier $x$ tels que : $$\underset{n}{\underbrace{11\cdots 1}}=x^2.(1)$$ D'après (1), $x$ est impair (en effet, (1) modulo 2, et notons que $x^2\equiv x(\mathrm{mod}2)$). De plus, $x\equiv 1(\mathrm{mod}4)$, puisque $2\nmid x$. Or $$\underset{n}{\underbrace{11\cdots 1}}-1=\underset{n-1}{\underbrace{11\cdots 10}}$$ est divisible par 2, pas par 4. Ceci veut dire que le membre de gauche de (1) est $\not\equiv 1(\mathrm{mod}4)$, une contradiction.

Exemple

En utilisant les chiffres $1,2,3,4,5,6$ et $7$, on peut obtenir des nombres à $7$ chiffres où chaque chiffre n'est utilisé qu'une seule fois (dans chaque nombre à $7$ chiffres). Montrer qu'il n'y a aucun de ces nombres qui soit un multiple d'un autre.

Supposons, par l'absurde, qu'il existe deux nombres différents, $a$ et $b$, à $7$ chiffres chacun et tels que $a=bc$ où $c>1$ est un entier naturel. Puisque la somme des chiffres, aussi bien de $a$ ou de $b$, est égale à : $1+2+3+4+5+6+7\equiv 1(\mathrm{mod}9)$, alors $a\equiv b\equiv 1(\mathrm{mod}9)$. En considérant l'équation $a=bc$ modulo $9$ on obtient $c\equiv 1(\mathrm{mod}9)$. Or $c>1$, donc $c\ge 10$, et $a\ge 10b>10^7$. Une contradiction car $a$ est un nombre à $7$ chiffres.

Exemple

On considère la suite $(x_n{)}_{n\ge 1}$ définie par $x_1=1,x_2=3$ et pour $n\ge 2,x_{n+1}=x_n+2x_{n-1}$. On considère la suite $(y_n{)}_{n\ge 1}$ définie par $y_1=7,y_2=17$ et pour $n\ge 2,y_{n+1}=2y_n+3y_{n-1}$. Montrer que les suites $(x_n{)}_{n\ge 1}$ et $(y_n{)}_{n\ge 1}$ n'ont aucun élément en commun.

On montre que la suite $(x_n{)}_{n\ge 1}$, modulo $8$, est périodique : $1,3,5,3,5,\cdots$ Comme $x_2\equiv 3,x_3\equiv 5(\mathrm{mod}8)$, si $x_{n-1}\equiv 3,x_n\equiv 5(\mathrm{mod}8)$, alors d'après la relation de récurrence vérifiée par la suite $(x_n{)}_{n\ge 1}$ on a : $$x_{n+1}=x_n+2x_{n-1}\equiv 5+2\times 3\equiv 3(\mathrm{mod}8),x_{n+2}=x_{n+1}+2x_n\equiv 3+2\times 5\equiv 5(\mathrm{mod}8).$$ On a ainsi montré par récurrence sur $n\ge 1$ que la suite $(x_n{)}_{n\ge 1}$ est périodique modulo $8$. On montre, de la même façon, que la suite $(y_n{)}_{n\ge 1}$ est périodique modulo $8$ : $7,1,7,1,7,1,\cdots$ Les suites $x_2,x_3,\cdots$ et $y_1,y_2,\cdots$ modulo $8$ n'ont aucun terme en commun. De plus, puisque $(y_n{)}_{n\ge 1}$ est strictement croissante, alors $y_1,y_2,\cdots$ ne peuvent pas être égaux à $x_1=1$, ce qui montre que les suites $(x_n{)}_{n\ge 1}$ et $(y_n{)}_{n\ge 1}$ n'ont aucun terme en commun.

Exemple

Soit $p$ un entier strictement positif donné. Déterminer la valeur minimale, strictement positive, de l'expression $(2p{)}^{2m}-(2p-1{)}^n$, où $m$ et $n$ sont deux entiers strictement positifs.

On se propose de montrer que cette valeur minimale recherchée est égale à : $$(2p{)}^2-(2p-1{)}^2=4p-1.$$ En effet, notons d'abord que puisque $(2p{)}^2=(4p-2)p+2p$ et $(2p-1{)}^2=(4p-2)(p-1)+(2p-1)$, alors : $$(2p{)}^{2m}-(2p-1{)}^n\equiv (2p)-(2p-1)\equiv 1(\mathrm{mod}4p-2).(1)$$ De plus, on doit montrer qu'il n'existe pas deux entiers strictement positifs $m$ et $n$ tels que $(2p{)}^{2m}-(2p-1{)}^n=1$. Sinon, alors : $$((2p{)}^m-1)((2p{)}^m+1)=(2p-1{)}^n.$$ Les deux diviseurs du membre de gauche de l'équation ci-dessus sont clairement premiers entre eux, mais le membre de droite est une puissance $n$-ème d'un certain entier. Donc : $$(2p{)}^m+1=a^n,(2)$$ où $a$ est un entier strictement positif, et $a|(2p-1)$. En considérant la relation (2) modulo $a$, alors le membre de gauche est : $$(2p-1+1{)}^m+1\equiv 1+1\equiv 2(\mathrm{mod}a),$$ ce qui implique que $2\equiv 0(\mathrm{mod}a)$. Or $a$ est clairement un entier impair strictement plus grand que $1$, une contradiction. En combinant avec (1) on sait que si $(2p{)}^{2m}-(2p-1{)}^n>0$ alors $(2p{)}^{2m}-(2p-1{)}^n\ge 4p-1$, et lorsque $m=1$ et $n=2$ on a égalité. Ceci permet de conclure que la valeur minimale recherchée est égale à $4p-1$.

Exemple

Soit $n>3$ un entier impair. Montrer qu'après avoir pris arbitrairement un élément de l'ensemble $S=\{0,1,\cdots ,n-1\}$ on peut toujours partager le reste des éléments en deux groupes, chaque groupe se compose de $\frac{n-1}{2}$ nombres, et les sommes des nombres des deux groupes sont congrues modulo $n$.

La première clé dans la résolution de ce problème est de remarquer que pour tout $x\in S\setminus \{0\}$, l'ensemble $S\setminus \{x\}$ peut être obtenu à partir de $T=\{1,2,\cdots ,n-1\}$ par la transformation : $$T+x(\mathrm{mod}n)=\{a+x(\mathrm{mod}n),a\in T\}.$$