Le théorème des restes chinois

Théorème

Si m₁, ..., m_n sont des entiers supérieurs à 2 deux-à-deux premiers entre eux, alors, pour des entiers a₁, ..., a_n, le système d'équations:

x mod m₁ = a₁
...
x mod m_n = a_n

admet une unique solution modulo M = m₁ · ... · m_n donnée par la formule:

x = (a₁M₁y₁ + ... + a_nM_ny_n) mod M

où M_i = M/m_i et y_i = M_i^-1 mod m_i pour 1 i n.

Exemple

Pour n = 3, supposons que m₁ = 7, m₂ = 11 et m₃ = 13. On a donc M = 1001.
On calcule M₁ = 143, M₂ = 91, M₃ = 77.
D'après l'algorithme d'Euclide étendu, on a y₁ = 5, y₂ = 4, y₃ = 12.
Par exemple, pour le système d'équations:

x mod 7 = 5
x mod 11 = 3
x mod 13 = 10
la formule donne pour solution:

x = (5·143·5 + 3·91·4 + 10·77·12) mod 1001
x = 13'907 mod 1001
x = 894 On peut facilement vérifier cette solution en introduisant x dans le système d'équations.

Exercice

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 reçoit alors 3 pièces. Mais les pirates se querellent, et 6 d'entre eux sont tués. Après un nouveau partage du même butin, le cuisinier reçoit 4 pièces. Dans un naufrage ultérieur, seuls le butin, 6 pirates et le cuisinier sont sauvés, et le partage donne alors 5 pièces d'or à ce dernier. Quelle est la fortune minimale que peut espérer le cuisinier s'il décide d'empoisonner les derniers pirates?

Solution

Références

Stinson Douglas, Cryptographie - Théorie et pratique, Vuibert Informatique, Paris, 2001, p. 105
Michel Van Caneghem, Congruences et théorème chinois des restes, février 2003

Didier Müller, 29.1.21