Sun Zi problème

NOMBRES – Curiosités, Théorie et Usages Accueil DicoNombre Rubriques Nouveautés Édition du: 05/12/2021 Orientation générale DicoMot Math Atlas Actualités M'écrire Barre de recherche DicoCulture Index alphabétique Références Brèves de Maths
	Arithmétique
Débutants Opérations	MODULO						Glossaire Nombres
Arithmétique et Théorie des nombres >>> INDEX		Introduction	Théorie		Propriétés	Formulaire
		Applications	Calculs		Carrés	Cubes
		Jeux	Sun Zi		Mod 9, 10, 11	Carrés et Cubes
		Parité	7 ^ 7 ^ 7		Log Modulaire	11¹⁰ = 32 mod 71
		45, 454 …
				Sommaire de cette page >>> Problème de Sun Zi >>> Essais >>> Essais final >>> Calculs (trois méthodes) >>> Calcul général >>> Procédure en un coup d'œil >>> Calcul en modules non premiers entre eux >>> Exemple 2, 3, 4, 5, 6, 7 >>> Exemple des 17 pirates >>> Anglais

Les RESTES chinois

Problème de Sun Zi

Systèmes d'équations avec les congruences.

Approche imagée; méthodes de résolution; exemples classiques.

Exemple

Question

Comment retrouver le nombre 52 à partir des restes 1, 2 et 3 ?

Voir Nombre 52

Nombres "chinois"

Nombres tels que n mod 3 = 1 et n mod 5 = 2:

7, 22, 37, 52, 67, 82, 97…

Avec n mod 7 = 3, en plus:

52, 157, 262, 367, 472, 577, 682, 787, 892, 997…

Avec n mod 11 = 4, en plus:

367, 1522, 2677, 3832, 4987, 6142, 7297, 8452, 9607…

Avec n mod 13 = 5, en plus:

14227, 29242, 44257, 59272, 74287, 89302…

Théorème des restes chinois

Pour tous (a, b) et (m, n) – m et n premiers entre eux – il existe un nombre unique x tel que:

m_n^-1 est l'inverse de m modulo n.

Voir Application des formules de congruences

Énoncé

Sun Zi (ou Sun Tzu), le mathématicien chinois, (vers l’an 300) s’intéresse à des problèmes qui nécessitent un raisonnement impliquant les restes des divisons. Il cite par exemple:

On ignore la quantité d’objets. Mais,

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 ?

La formulation exacte serait:

Combien l'armée de Han Xing comporte-t-elle de soldats si, rangés par 3 colonnes, il reste deux soldats, rangés par 5 colonnes, il reste trois soldats et, rangés par 7 colonnes, il reste deux soldats ?

Essais

Il faut au moins 7 objets pour les mettre en rang par 7. Le premier cas répondant à un des critères est 7 + 2 ; Ce nombre répond-il aussi aux deux autres critères (consigne).

La quantité 9 n’est pas suffisante. Elle satisfait le cas 7, mais par les cas 3 et 5.

L’essai suivant se fera avec 2 x 7 + 2 = 16.

La quantité 9 n’est pas suffisante. Elle satisfait le cas 7, mais par les cas 3 et 5.

Essais final donnant le résultat escompté

L’essai suivant se fera avec 3 x 7 + 2 = 23.

Bingo ! 23, c’est la bonne solution.

Les solutions suivantes sont 128, 233, 338, 443, 548 …

Solution générique : 23 + 105k, en notant que 3 x 5 x 7 = 105.

En exigeant un reste égal à 2 pour les trois divisions
la solution serait 105k + 107.

Calculs (3 méthodes)

Équations

Mise en équation de l'énoncé et résolution classique.

3a + 2 = 5b + 3 = 7c + 2

3a = 7c

a = 7c / 3 et c est un multiple de 3

À ce stade, il faut faire des essais:

Si c = 3 => a = 7x3 /3 = 7

Et 5b + 3 = 7x3 + 2 => 5b = 20 => b = 4

Bilan: a = 7, b = 4, c= 3 et les termes de l'égalité valent 23.

Congruences – liste

On liste les valeurs successives des nombres modulo 3, puis 5, puis 7.

On cherche la concordance.

X mod 3 = 2 => X = {2, 5, 8, 11, 14, 17, 20, 23, 26 …}

X mod 5 = 3 => X = { 3, 8, 13, 18, 23, 28 …}

X mod 7 = 2 => X = {2, 9, 16, 23, 30 …}

Congruences – restes

On liste des nombres selon le module le plus grand (ici 7)

Puis, les restes de ces nombres selon les autres modulos.

On cherche les restes tels que demandés dans le problème.

X mod 7 = 2 => X = {2, 9, 16, 23, 30 …}

mod 5 {2, 4, 1, 3, 0 …}

mod 3 {2, 0, 1, 2, 0 …}

Calcul général

– Théorème des restes chinois

Il s'agit du problème général des restes chinois: on connaît les restes modulo divers nombres, il faut trouver le nombre en question.

Il n'est pas simple d'écrire les formules générales de calcul, mieux vaut dérouler un exemple. Le problème de SunZi est pris comme exemple.

Formellement, il s'agit de résoudre un système d'équations dans le monde des congruences. Le problème de Sun Zi s'écrit:

Écriture 1

Écriture 2

X mod 3 = 2

X mod 5 = 3

X mod 7 = 2

X 2 (mod 3)

X 3 (mod 5)

X 2 (mod 7)

Voici la procédure qui permet d'obtenir la solution dans le cas général:

1. On calcule le produit des modules.

N = 3 x 5 x 7 = 105

2. Pour chaque module, on calcule le produit des autres modules.

N₃= 5 x 7 = 35

N₅= 3 x 7 = 21

N₇= 3 x 5 = 15

3. Pour chacun de ces nombres, on cherche un multiple dont le reste est 1 dans son modulo.
Avec 15 et 21, la solution est immédiate. Avec 35, il faut prendre deux fois cette valeur pour obtenir un reste égal à 1.

N₇= 15

N₇ 1 (mod 7) – OK 15

N₅= 21

N₅ 1 (mod 5) – OK 21

N₃= 35

N₃ 2 (mod 3) – mauvais

2N₃= 70

2N₃ 1 (mod 3) – OK 70

4. Somme des produits de ces nombres par les restes correspondants.
Le résultat est une solution.

X = 70 x 2 + 21 x 3 + 15 x 2

= 233

5. Solution minimale et
solution générique.

X_Min = 233 – 2 x 105 = 23

X_Gén = 23 + 105k

Procédure en un coup d'œil (avec deux restes)

Voir Exemple pratique (tour de magie)

Modules non-premiers entre eux
La procédure exposée ci-dessus fonctionne lorsque les modules sont premiers entre eux. Si ce n'est pas le cas, on utilise les PGCD et PPCM. Mais, il n'y a pas toujours une solution: Théorème Si X n₁ (mod m₁) et X n₂ (mod m₂) avec G = PGCD (m₁, m₂) et L = PPCM (m₁, m₂). Il existe une solution si et seulement si n₁ n₂ (mod G). La solution est unique modulo L. Exemple: X 3 (mod 4) X 5 (mod 6)
1. Module de la solution.	N = PPCM(4,6) = 2 x 2 x 3 = 12
2. Changement de système pour obtenir des modules premiers entre eux. Théorème: le reste est conservé pour les multiples du modulo.	X 3 (mod 4) X 3 (mod 2) => X 1 (mod 2) X 5 (mod 6) X 5 (mod 2) => X 1 (mod 2) X 5 (mod 3) => X 2 (mod 3)
3. On conserve les modules tels que le produit donne bien le PPCM. En fait, on élimine les équations avec le PGCD comme module (Ici: 2).	X 3 (mod 4) qui contient bien X 1 (mod 2) X 2 (mod 3)
4. Calculs des N_i	N = 12 N₄= 3 N₃= 4
5. Recherche des restes à 1	N₄= 3 -1 x N₄ 1 (mod 4) – OK –3 (on peut aussi faire 3N₄) N₃= 4 N₄ 1 (mod 3) – OK 4
6. Solutions	X = –3 x 3 + 4 x 2 = –1 X = 11 + 12k

Autre exemple
Exemple: X 1 (mod 4) X 5 (mod 18)
1. Module de la solution.	N = PPCM(4,18) = 36
2. Changement de système	X 1 (mod 4) X 1 (mod 2) X 5 (mod 18) X 5 (mod 2) => X 1 (mod 2) X 5 (mod 9)
3. Système équivalent	X 1 (mod 4) X 5 (mod 9)
4. Calculs des N_i	N = 36 N₄= 9 N₉= 4
5. Recherche des restes à 1	N₄= 9 N₄ 1 (mod 4) – OK 1 N₉= 4 N₉ 4 (mod 9) – non 7N₉ 28 (mod 9) 1 (mod 9) – OK 28
6. Solutions	X = 9 x 1 + 28 x 5 = 149 X = 5 + 36k

Résumé pour calcul express (cas d'un PGCD = 2)

Exemple 2, 3, 4, 5, 6, 7
X 1 (mod 2) inclus dans 4 X 1 (mod 3) OK X 1 (mod 4) OK X 1 (mod 5) OK X 1 (mod 6) inclus dans 2 en fait 4 et 3 X 0 (mod 7) OK
1. Coefficients	N = 420 N₃= 140 N₄= 105 N₅= 84 N₇= 60
2. Restes à 1	2N₃= 140 1 (mod 3) – OK 140 N₄= 105 1 (mod 4) – OK 105 –N₅= –84 –1 (mod 5) – OK –84 2N₇= 120 1 (mod 7) – OK 120
3. Somme	X = 140 x 1 + 105 x 1 – 84 x 1 + 120 x 0 = 301 X = 301 + 420k

Résumé pour calcul express (cas d'un PGCD = 1)

Exemple des 17 pirates
Dix-sept pirates possèdent un trésor en pièces d'or de même valeur. Partagé en parts égales, il reste trois pièces données au cuisinier. Six pirates sont tués, le partage laisserait 4 pièces pour le cuisinier. Après un naufrage, le trésor est intact et les six rescapés se partagent le trésor tout en laissant 5 pièces au cuisinier. Quelle est la valeur minimale du trésor? X 3 (mod 17) X 4 (mod 11) X 5 (mod 6)
4. Coefficients	N = 1 122 N₁₇= 66 N₁₁= 102 N₆= 187
5. Restes à 1	3N₁₇= 528 1 (mod 17) 4N₁₇= 408 1 (mod 11) 1N₁₇= 187 1 (mod 6)
6. Somme	X = 528x3 + 408x4 + 187x5 = 4 151 X = 785 + 1 122k Valeur minimale du trésor: 785 pièces d'or.

ENGLISH CORNER

Chinese Remainder Theorem.

The following problem was posed by Sun ZI: there are certain things whose number is unknown. Repeatedly divided by 3, the remainder is 2; by 5 the remainder is 3; and by 7 the remainder is 2. What will be the number?

The notion of modular arithmetic is related to that of the remainder in division. The operation of finding the remainder is sometimes referred to as the modulo operation.

Retour	Autre exemple de calcul Approche Équations avec les congruences
Voir	Jeux – Index Équations Divisibilité Clé de divisibilité, une application de la théorie du modulo La division Exemple d'application du modulo en Codage RSA Puzzle 45, 454, 4545,45454
Aussi	Bœufs d'Hélios Calcul mental Géométrie Nombres Premiers Nombres Rationnels Preuve par 9 – Glossaire Théorie des nombres Variations sur les carrés
Site	Théorème des restes chinois – Wikipédia A. Bogomolny, Chinese Remainder Theorem from Interactive Mathematics Miscellany and Puzzles
Cette page	http://villemin.gerard.free.fr/ThNbDemo/ModSunZi.htm

Référence de cette page

Les restes chinois – Problème de Sun Zi
http://villemin.gerard.free.fr/ThNbDemo/ModSunZi.htm