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.

6.4 Théorème des restes chinois

Dans ce paragraphe on étudie les équations linéaires et les systèmes d'équations faisant intervenir des congruences. On considère, tout d'abord, les congruences du type :

$$ax\equiv b(\mathrm{mod}n),$$

où $a,b$ et $n$ sont des entiers donnés tels que $a\ne 0$ et $n>1$. On cherche les $x\in \mathbb{Z}$ vérifiant cette congruence. Comme cas particulier on a :

Définition

On dit que $a$ est inversible modulo $n$ s'il existe $x\in \mathbb{Z}$ tel que $ax\equiv 1(\mathrm{mod}n)$.

Proposition

Un entier $a$ est inversible modulo $n$ si, et seulement si, $\gcd (a,n)=1$. Dans ce cas, deux inverses quelconques de $a$, modulo $n$, sont congrus modulo $n$.

Preuve

Si $a$ est inversible modulo $n$, alors il existe $x\in \mathbb{Z}$ tel que $ax\equiv 1(\mathrm{mod}n)$. Donc, il existe $y\in \mathbb{Z}$ tel que $ax=ny+1$, c'est-à-dire $xa+(-y)n=1$. D'où $\gcd (a,n)=1$.

Réciproquement, comme $\gcd (a,n)=1$, alors d'après le théorème de Bézout il existe $x,y\in \mathbb{Z}$ tels que $ax+ny=1$, par suite $ax\equiv 1(\mathrm{mod}n)$.

Finalement, si $x$ et $y$ sont deux inverses de $a$ modulo $n$, on a alors : $ax\equiv 1\equiv ay(\mathrm{mod}n)$, d'où $ax\equiv ay(\mathrm{mod}n)$. Comme $\gcd (a,n)=1$ alors on en déduit que $x\equiv y(\mathrm{mod}n)$. Par conséquent, $a$ admet, modulo $n$, un seul inverse.

Corollaire

Soient $a$ et $p$ deux entiers avec $p$ premier. Alors, $a$ est inversible modulo $p$ si, et seulement si, $p\nmid a$. De plus, dans ce cas, l'inverse de $a$ modulo $p$ est unique.

Proposition

Soient $a,b,n$ des entiers avec $n>1$. Si $a$ est inversible modulo $n$, alors la congruence $ax\equiv b(\mathrm{mod}n)$ admet une seule solution modulo $n$, à savoir :

$$x\equiv a^{\varphi (n)-1}b(\mathrm{mod}n).$$

En particulier, tout inverse de $a$, modulo $n$, est congru à $a^{\varphi (n)-1}$, modulo $n$.

Preuve

Si $a$ est inversible modulo $n$, alors $\gcd (a,n)=1$. Donc, en appliquant le théorème d'Euler on a :

$$ax\equiv b(\mathrm{mod}n)⟺a^{\varphi (n)}x\equiv a^{\varphi (n)-1}b(\mathrm{mod}n)⟺x\equiv a^{\varphi (n)-1}b(\mathrm{mod}n).$$

Théorème des restes chinois

Soient $m_1>1,m_2>1,\dots ,m_k>1$ des entiers deux à deux premiers entre eux. Pour des entiers arbitraires donnés $a_1,a_2,\dots ,a_k$, le système de congruences :

$$\begin{cases} x \equiv a_1 \pmod{m_1}\\ x \equiv a_2 \pmod{m_2}\\ \vdots\\ x \equiv a_k \pmod{m_k} \end{cases}$$

admet une solution unique, modulo $m_1{m}_2\cdots m_k$. En d'autres termes, il existe un unique entier $0\le y<m_1{m}_2\cdots m_k$ tel que $x\in \mathbb{Z}$ vérifie le système ci-dessus si, et seulement si :

$$x\equiv y(\mathrm{mod}{m}_1{m}_2\cdots m_k).$$

Démonstration

Notons, tout d'abord, que si $x_1$ et $x_2$ sont deux solutions quelconques du système de congruence, alors :

$$x_1\equiv a_i\equiv x_2(\mathrm{mod}{m}_i),i=1,2,\dots ,k.$$

Or comme $m_1,m_2,\dots ,m_k$ sont deux à deux premiers entre eux, on déduit que :

$$x_1\equiv x_2(\mathrm{mod}{m}_1{m}_2\cdots m_k).$$

Donc, si le système de congruence admet une solution, alors elle est unique modulo $m_1{m}_2\cdots m_k$.

Pour montrer l'existence d'une solution, posons, pour $1\le j\le k$, $y_j=\prod _{1\le i\ne j\le k}{m}_i$ de sorte que $\gcd (y_j,m_j)=1$. Soient $b_j$ l'inverse de $y_j$ modulo $m_j$, et $x=\sum _{j=1}^k{a}_j{b}_j{y}_j$. Pour un $1\le l\le k$ fixé, on a : $y_j\equiv 0(\mathrm{mod}{m}_l)$ dès que $j\ne l$. Donc, modulo $m_l$, on a :

$$x\equiv a_l{b}_l{y}_l\equiv a_l\cdot 1\equiv a_l(\mathrm{mod}{m}_l).$$

Le théorème des restes chinois peut s'énoncer aussi sous la forme équivalente suivante :

Théorème des restes chinois (forme alternative)

Soient $m_1,m_2,\dots ,m_k$ des entiers strictement positifs deux à deux premiers entre eux, $M=m_1{m}_2\cdots m_k$, $M_i=\frac{M}{m_i}$ ($i=1,2,\dots ,k$), et $b_1,b_2,\dots ,b_k$ des entiers. Alors, le système de congruences :

$$x\equiv b_1(\mathrm{mod}{m}_1),x\equiv b_2(\mathrm{mod}{m}_2),\dots ,x\equiv b_k(\mathrm{mod}{m}_k)$$

admet une unique solution

$$x\equiv M_1^{\ast }{M}_1{b}_1+M_2^{\ast }{M}_2{b}_2+\cdots +M_k^{\ast }{M}_k{b}_k(\mathrm{mod}M)$$

où $M_i^{\ast }$ sont des entiers tels que $M_i^{\ast }{M}_i\equiv 1(\mathrm{mod}{m}_i)$ ($i=1,2,\dots ,k$).

Exemple : Entiers consécutifs avec diviseur carré

Montrer que pour tout $n\in {\mathbb{N}}^{\ast }$, il existe $n$ entiers strictement positifs consécutifs tels que chacun de ces entiers possède un diviseur carré strictement supérieur à $1$.

Comme il y a une infinité de nombres premiers, on peut trouver $n$ nombres consécutifs différents $p_1,p_2,\dots ,p_n$. Considérons le système de congruences suivant :

$$x\equiv -i(\mathrm{mod}{p}_i^2),i=1,2,\dots ,n.(1)$$

Puisque $p_1^2,p_2^2,\dots ,p_n^2$ sont deux à deux premiers entre eux, alors d'après le théorème des restes chinois on sait que le système $(1)$ admet une solution entière strictement positive. Donc $n$ entiers consécutifs $x+1,x+2,\dots ,x+n$ sont divisibles par $p_1^2,p_2^2,\dots ,p_n^2$ respectivement.

Remarque 1 : Si nous n'utilisons pas directement les nombres premiers, nous pouvons également adopter la variante suivante. Puisque les nombres de Fermat $F_k=2^{2^k}+1$ sont deux à deux premiers entre eux, après avoir remplacé $p_i^2$ dans $(1)$ par $F_i^2$ ($i=1,2,\dots ,n$), le système de congruences correspondant a aussi une solution, ce qui donne le même résultat.

Remarque 2 : La solution de cet exemple montre une application de base du théorème des restes chinois. Il réduit le problème « trouver $n$ entiers consécutifs possédant une certaine propriété » en « trouver $n$ nombres deux à deux premiers entre eux possédant une certaine propriété », et ce dernier est plus facile à résoudre.

Exemple : Entiers non-puissances

Montrer que pour tout $n\in {\mathbb{N}}^{\ast }$, il existe $n$ entiers strictement positifs consécutifs tels que tous ces nombres ne sont pas des nombres de puissance (un entier $N$ est appelé un nombre de puissance si chaque puissance d'un diviseur premier dans sa décomposition primaire est strictement supérieure à $1$, c'est-à-dire $N=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$ avec ${\alpha }_i>1$ pour $i=1,2,\dots ,k$).

On va montrer qu'il existe $n$ entiers strictement positifs consécutifs, parmi lesquels chaque nombre a au moins un diviseur premier qui n'apparaît qu'une seule fois dans sa décomposition primaire, donc ce n'est pas un nombre de puissance. Pour cela on choisit $n$ nombres premiers différents $p_1,p_2,\dots ,p_n$, et on considère le système de congruences :

$$x\equiv -i+p_i(\mathrm{mod}{p}_i^2),i=1,2,\dots ,n.(1)$$

Puisque $p_1^2,p_2^2,\dots ,p_n^2$ sont deux à deux premiers entre eux, d'après le théorème des restes chinois le système ci-dessus admet une solution entière strictement positive. Comme $x+i\equiv p_i(\mathrm{mod}{p}_i^2)$ pour $1\le i\le n$, alors $p_i|(x+i)$. Or, par $(1)$, on sait que $p_i^2\nmid (x+i)$, c'est-à-dire $p_i$ apparaît uniquement une seule fois dans la décomposition primaire de $x+i$, par conséquent aucun de $x+1,x+2,\dots ,x+n$ n'est un nombre de puissance.

Exemple : Fonction somme des diviseurs

Pour $n\in {\mathbb{N}}^{\ast }$ donné, soit $f(n)$ le plus petit entier strictement positif tel que $\sum _{k=1}^{f(n)}k$ soit divisible par $n$. Montrer que $f(n)=2n-1$ si, et seulement si, $n$ est une puissance de $2$.

Si $n=2^m$, alors d'une part

$$2\sum _{k=1}^{n-1}k=\frac{(2n-1)\times 2n}{2}=(2^{m+1}-1)\cdot 2^m$$

est divisible par $2^m=n$. D'autre part, si $r\le 2n-2$, alors $\sum _{k=1}^{r}k=\frac{r(r+1)}{2}$ n'est pas divisible par $2^m$ car l'un de $r$ ou $r+1$ est impair et l'autre est plus petit que $(2n-2)+1=2^{m+1}-1$, donc non divisible par $2^{m+1}$. Ainsi, on a montré que $f(2^m)=2^{m+1}-1$.

On suppose que $n$ n'est pas une puissance de $2$, c'est-à-dire $n=2^{m}a$ avec $a>1$ impair. On veut montrer qu'il existe un entier strictement positif $r<2n-1$ tel que $2^{m+1}|r$ et $a|(r+1)$, donc $\sum _{k=1}^{r}k=\frac{r(r+1)}{2}$ est divisible par $2^{m}a=n$, d'où $f(n)<2n-1$. Pour montrer cette assertion on considère :

$$x\equiv 0(\mathrm{mod}{2}^{m+1}),x\equiv -1(\mathrm{mod}a).(1)$$