Le théorème des restes chinois

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) :

Si a b (mod n) et c d (mod n) alors a + c b + d (mod n)
Si a b (mod n) et c d (mod n) alors ac bd (mod n)
Si ac bc (mod n) et pgcd(c,n) = 1 alors a b (mod n) (théorème de Gauss)

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 m₁, m₂, ..., m_k, premiers entre eux deux à deux, et k entiers r₁, r₂, ..., r_k. Le système de congruences admet une unique solution modulo M = m₁ m₂... m_k.

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

Posons M_i = pour i = 1, 2, ..., k. On a donc pgcd(M_i, m_i) = 1 et on peut ainsi trouver d'après l'identité de Bezout deux entiers u_i et v_i tel que M_iu_i + m_iv_i = 1.
On a alors : u₁M₁r₁ + u₂M₂r₂ + ... + u_kM_kr_k r_i (mod m_i) pour i = 1, 2, ..., k
Par conséquent le nombre x = u₁M₁r₁ + u₂M₂r₂ + ... + u_kM_kr_k est solution du système. De plus si y est une autre solution de celui-ci, alors m_i 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 = u₁M₁r₁ + u₂M₂r₂ + ... + u_kM_kr_k + 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 = u₁×11×6×3 + u₂×17×6×4 + u₃×17×11×5 + n×17×11×6
ou encore x = 198u₁ + 408u₂ + 935 u₃ + 1122n.
Il reste à trouver les u_i:

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 u₁ = 8.

De la même manière, on trouve u₂ = 4 et u₃ = 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.