L'histoire du théorème des restes chinois commence… en Chine, sous forme d'énigmes. La suivante est due au mathématicien et astronome Sun Zi, qui vécut entre le IIIe et le Ve siècle de notre ère (et qui ne doit pas être confondu avec le général Sun Zi) :
> « Quand le général Han Xing range ses soldats par trois, il reste deux soldats, quand il les range par cinq, il en reste trois et quand il les range par sept, il en reste deux. Combien l'armée de Han Xing comporte-t-elle de soldats ? »
Derrière l'habillage ludique, il s'agit d'un problème d'arithmétique lié à la divisibilité. Sans encore le résoudre, on peut remarquer que, s'il a une solution, on en obtient une autre en ajoutant cent cinq soldats car 105 est multiple de 3, 5 et 7 ce qui, en itérant cette remarque, en produit une infinité. On en déduit que, si une solution existe, il en existe une entre 1 et 105. L'énigme est ainsi potentiellement résolue, puisqu'il suffit alors d'essayer un nombre fini de valeurs !
Cependant, cette démarche est fastidieuse et peu éclairante. Il est préférable de répondre séparément aux trois conditions posées. Pour qu'il reste deux soldats quand on les groupe par trois, l'effectif total doit être l'un des nombres 2, 5, 8, 11, 14, 17, 20, 23, 26, 29… Pour qu'il en reste trois quand on les groupe par cinq, l'effectif doit être l'un des nombres 3, 8, 13, 18, 23, 28… Enfin, pour qu'il en reste deux quand on les range par sept, l'effectif total doit être l'un des nombres 2, 9, 16, 23, 30… Le nombre 23 appartient aux trois suites, donc il s'agit d'une solution au problème, et c'est la plus petite. Les autres sont 128, puis 233, et ainsi de suite en ajoutant 105 à chaque fois. Cette démarche est déjà plus claire, mais on peut s'enfoncer davantage dans les rouages de la question. Pour cela, il est utile d'introduire une nouvelle vision des nombres, celle de l'arithmétique modulaire.
-