Le Théorème des Restes Chinois

On trouve des traces de ce résultat, que nous vous avons proposé en exercice, dans les travaux mathématiques d'à peu près tous les pays, du Sunzi suanji («Classique de calcul de Sunzi»), au Liber Abaci de Fibonacci, en passant par Aryabhata et Brahmagupta en Inde, ainsi que par les mathématiciens arabes Ibn Tahir et al-Haytham ; mais curieusement, il n'est pas énoncé par les grecs. Au travers de ses multiples généralisations, le théorème des restes chinois est à la base de nombreux algorithmes de calcul arithmétique et symbolique, ainsi que de méthodes de cryptographie.

Le Sunzi suanji n'a pas pu être daté précisément : probablement entre le III^eet le VI^esiècle. Voici le problème 26, chapitre 3¹.

Soit des objets dont on ignore le nombre. En les comptant 3 par 3 il en reste 2 ; en les comptant 5 par 5, il en reste 3 et en les comptant 7 par 7, il en reste 2. Combien y a-t-il d'objets ?

Réponse : 23.

Règle : «En comptant par 3, il en reste 2» : poser 140 ; «En comptant par 5, il en reste 3» : poser 63 ; «En comptant par 7, il en reste 2» : poser 30. Faire la somme de ces 3 nombres, obtenir 233. Soustraire 210 de ce total, d'où la réponse.

En général : pour chaque unité restante d'un décompte par 3, poser 70 ; pour chaque unité restante d'un décompte par 5, poser 21 ; pour chaque unité restante d'un décompte par 7, poser 15. Si la somme ainsi obtenue vaut 106 ou plus, ôter 105 pour trouver la réponse.

Si vous avez bien compris le théorème, vous ne devriez pas avoir de peine à retrouver les nombres que Sunzi recommande de «poser», et à reconnaître le produit $3\times 5\times 7=105$.

Tant que vous y serez, renseignez le cuisinier sur son bateau de pirates :

Dix-sept pirates s'emparent d'un lot de pièces d'or toutes identiques. Leur loi exige un partage à égalité : chacun doit recevoir le même nombre de pièces d'or et, s'il en reste, elles sont attribuées au cuisinier de bord. Dans le cas présent, la part du cuisinier serait de trois pièces, mais les pirates se querellent et six d'entre eux sont tués, ce qui porte la part du cuisinier à quatre pièces. Au cours d'une terrible tempête, le bateau fait naufrage et ne survivent que six pirates et le cuisinier. Par bonheur, le butin est sauvé. La part du cuisinier est maintenant de cinq pièces. Que peut espérer gagner le cuisinier lorsqu'il décide d'empoisonner le reste de l'équipage, sachant que c'est la plus petite des solutions possibles ?