Théorème chinois des restes
Description
Ce théorème est en quelque sorte une reformulation/utilisation de l'identité de Bezout, ce qui chronologiquement faux. Pourtant il est facilement retrouvable grâce à cet outil.
Théorème
Problème
Si m₁, m₂, …, m_n sont des entiers supérieurs à 2, premiers deux à deux entre eux, et r₁, r₂, …, r_n des entiers, alors, le nombre minimal x congrus à tous les r_i (mod m_i) correspond au système d'équations suivant:
⎧ x ≡ r₁ (mod m₁) ⎪ x ≡ r₂ (mod m₂) ⎨ … ⎪ … ⎩ x ≡ r_n (mod m_n)
La solution x est modulo M = m₁*·*m₂*·…·*m_n.
Solution
L'unique solution de ce problème est produite par la formule:
x = r₁*·*M₁*·*y₁*+…+*r_n*·*M_n*·*y_n (mod M)
où M_i = M/m_i et y_i = M⁻ⁱ_i (mod m_i) pour 1≦*i*≦n.
Exemple classique des pirates
Ennoncé
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 alors 3 pièces. Mais les pirates se querellent, et six d'entre eux sont tués. Le cuisinier recevrait alors 4 pièces. Dans un naufrage ultérieur, seuls le butin, six pirates et le cuisinier sont sauvés, et le partage donnerait alors 5 pièces d'or à ce dernier. Quelle est la fortune minimale que peut espérer le cuisinier quand il décide d'empoisonner le reste des pirates?
Premier partage
Si les 17 pirates se partagent le butin x à part égale P₁, il reste 3 pièces d'or pour le cuisinier. Ce reste correspond au reste de x ÷17, donc:
x ≡ 3 (mod 17).
Second partage
Après leur dispute, il ne reste plus que 11 pirates.
Si les 11 pirates se partagent le butin x à part égale P₂, il reste 4 pièces d'or pour le cuisinier. Ce reste correspond au reste de x ÷11, donc:
x ≡ 4 (mod 11).
Troisème partage
Après leur naufrage, il ne reste plus que 6 pirates.
Si les 6 pirates se partagent le butin x à part égale P₃, il reste 5 pièces d'or pour le cuisinier. Ce reste correspond au reste de x ÷11, donc:
x ≡ 5 (mod 6).
Système d'équation
Nous nous retrouvons donc avec le système d'équation suivant:
⎧ x ≡ 3 (mod 17) ⎨ x ≡ 4 (mod 11) ⎩ x ≡ 5 (mod 6)
M = 17·11·6 = 1122
x = 3·*M₁*·*y₁* + 4·*M₂*·*y₂* + 5·*M₃*·*y₃* (mod M)
où M₁ = M/17 = 66 ; M₂ = M/11 = 102 ; M₃ = M/6 = 187
les y_i.
Pour y₁, nous avons 66 = 17·3 + 15, 17 = 15·1 + 2 et 15 = 7·2 + 1 d'où 1 = 15 - 7·2 ce qui donne 1 = 15 - 7·(17 - 15).
Nous pouvons enfin trouver: 1 = 7·17 + 8·(66-17·3), ce qui donne: 1 = 8·66 - 17·17 donc 8 (mod 17)
- y₁ = 8 mod(17)
- y₂ = 4 mod(11)
- y₃ = 1 mod(6)
Solution
x ≡ 3·66·8 + 4·102·4 + 5·187·1 (mod 1122)
Donc x ≡ 785 (mod 1122).
Le minimum est de 785 pièces d'or.