Le théorème des restes chinois

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?

Corrigé

Si x est la fortune espérée du cuisinier, x est le plus petit entier positif tel que : x mod 17 = 3
x mod 11 = 4
x mod 6 = 5 Appliquons le théorème des restes chinois :

M = 17·11·6 = 1122,
M1 = 1122/17 = 66,
M2 = 1122/11 = 102,
M3 = 1122/6 = 187.

L'inversion de chaque Mi donne (avec l'algorithme d'Euclide étendu) :

y1 = 66-1 mod 17 = 8,
y2 = 102-1 mod 11 = 4,
y3 = 187-1 mod 6 = 1.

On obtient donc : x = (3·66·8 + 4·102·4 + 5·187·1) mod 1122 = 785.

785 pièces d'or ! Voilà qui pourrait pousser au meurtre...

Didier Müller, 2.3.02