Le théorème des restes chinois
ou comment résoudre des systèmes de congruences ?

 

 Avant de vouloir résoudre un système de congruences peut-être faut il rappeler ce qu'est une congruence :

On dit que a et b sont congrus modulo n (n > 1)  si n divise a - b. On écrit a b (mod n), notation introduite par Gauss.
C'est donc une autre façon de parler de divisibilité. Ainsi a  0 (mod n) signifie que n divise a (ou que le reste de la division de a par n est nul).
On a alors les propriétés suivantes (d'après les propriétés de la division) :

Rappelons aussi l'identité de Bezout :

Si a et b sont premieurs entre eux, alors il existe u et v entiers tels que au + bv = 1.

Venons-en à notre problème : comment résoudre le système de congruences suivant : ?

C'est le théorème des restes chinois qui nous fournit la réponse :

Soit k nombres entiers naturels m1, m2, ..., mk, premiers entre eux deux à deux, et k entiers r1, r2, ..., rk. Le système de congruences admet une unique solution modulo M = m1 m2... mk.

La preuve permettant de construire une solution de ce système, celle-ci est fournit ci-dessous :

Posons Mi = pour i = 1, 2, ..., k. On a donc pgcd(Mi, mi) = 1 et on peut ainsi trouver d'après l'identité de Bezout deux entiers ui et vi tel que  Miui + mivi = 1.
On a alors : u1M1r1 + u2M2r2 + ... + ukMkrk ri (mod mi) pour i = 1, 2, ..., k
Par conséquent le nombre x = u1M1r1 + u2M2r2 + ... + ukMkrk est solution du système. De plus si y est une autre solution de celui-ci, alors mi divise x - y pour chaque i = 1, 2, ..., k. Ainsi x - y est divisible par M. Le système admet donc une seule solution modulo M. Autrement dit, les solutions du système sont de la forme x = u1M1r1 + u2M2r2 + ... + ukMkrk + nM avec n entier.

Un exemple d'application très connu :

Une bande de 17 pirates s'est emparée d'un butin composé de pièces d'or d'égale valeur. Ils décident de se les partager également et de donner le reste au cuisinier chinois. Celui-ci recevrait trois pièces. Mais les pirates se querellent et six d'entre eux sont tués. Le cuisinier recevrait alors 4 pièces. Survient alors un naufrage et seuls 6 pirates, le cuisinier et le trésor sont sauvés et le partage laisserait 5 pièces d'or à ce dernier. Quelle est alors la fortune minimale que peut espérer ce dernier s'il décide d'empoisonner le reste des pirates ? 

 Solution :
Il s'agit de trouver x positif et minimal vérifiant le système
D'après le théorème des restes chinois (puisque 17, 11 et 6 sont premiers entre eux deux à deux), les solutions sont de la forme : x = u1×11×6×3 + u2×17×6×4 + u3×17×11×5 + n×17×11×6
ou encore x = 198u1 + 408u2 + 935 u3 + 1122n.
Il reste à trouver les ui :

On a par division euclidienne :
66 = 3×17 + 15
17 = 1×15 + 2
15 = 7×2 + 1
On en déduit que 1 = 15 - 7×2 et puisque 2 = 17 - 1×15, on a 1 = 15 - 7(17 - 1×15) c'est-à-dire 1 = 8×15 - 7×17.
Mais 15 = 66 - 3×17 d'où 1 = 8(66 - 3×17) - 7×17. On obtient pour finir 1 = 8×66 - 31×17 et u1 = 8.

De la même manière, on trouve u2 = 4 et u3 = 1.
Donc x = 198×8 + 408×4 + 935 + 1122n = 4151 + 1122n.

4151 est donc une solution possible pour notre cuisinier, mais ce n'est pas la plus petite. Il suffit d'effectuer la division de 4151 par 1122 pour trouver comme reste 785 qui est le nombre minimal de pièces que peut obtenir le cuisinier.

 

Un autre exemple d'application du théorème des restes chinois se trouve à la page du problème du mois de février 2002.