Le théorèmes des restes chinois

Théorème des restes chioins

Théorème : Prenons m₁, ..., m_n des entiers supérieurs à 2 deux à deux premiers entre eux, et a₁,...,a_n des entiers. Le système d'équations :

x=a₁ mod m₁
...
x=a_n mod m_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 i compris entre 1 et n.

Exemple : 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?

Si x est ce nombre, x est le plus petit entier positif tel que :

x=3 mod 17.
x=4 mod 11.
x=5 mod 6.

On applique le théorème chinois : on a M=17×11×6=1122, M₁=66, M₂=102, M₃=187. L'inversion de chaque M_i (par l'algorithme d'Euclide) donne y₁=8, y₂=4, y₃=1.

On obtient donc : x=3×66×8+4×102×4+5×187×1 mod 1122 = 785 mod 1122.
785 pièces d'or, voila qui reste particulièrement motivant!

Et encore, dans la cryptographie expliquée...

Les entiers modulo n.
L'algorithme d'Euclide, et son application aux calculs des clés secrètes du RSA [javascript].
Le symbole de Legendre, et son application aux tests de primalité probabilistes.
Comment fabriquer de grands nombres premiers? [applet java].
L'indicateur d'Euler.
La factorisation des entiers.
Le plan de la partie : Compléments.