Théorème des restes chinois

[loic7]

Bonjour j'ai un petit soucis sur un exercice :

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 ?

On a le système suivant :

x=2[3]
x=3[5]
x=2[7]


On a alors : x= u(1)*3*5*2+u(2)*3*7*3+u(3)*5*7 *2+n*3*5*7

Le but est alors de trouver u(1),u(2) et u(3)

On a 15=7*2+1 ==> 1=15-7*2 d'ou u(1)=1

35=3*11+2
11=2*5+1
==> 1=11-2*5=11-5*(35-3*11)=11*16-5*35 d'où u(3)=-5

21=5*4+1
==>1=21-5*4 d'où u(2)=1

on a x=3*5*2+3*7*2-5*5*7*2+n*3*5*7= GROS PROBLEME J'AI QUELQUE CHOSE DE NEGATIF
-----

[invite292e91f0]

Bonjour,
Trouver un résultat négatif n'est pas bien grave quand on travaille avec des modulo : tu ajoutes autant de fois 3*5*7 que nécessaire pour que ce soit positif. Ce qui compte, c'est que ton x vérifie bien ton système de départ...
Et là par contre j'ai des doutes. Si je ne me suis pas trompé, tu trouves 37 modulo 105 alors que tu devrais trouver 23 modulo 105 (encore une fois, je peux me planter). Es-tu sûr d'avoir bien appliqué ton cours sans erreur ?

[loic7]

on a x=3*5*2+3*7*3-5*5*7*2+n*3*5*7= -257 + 105 n

Quelqu'un voit-il une erreur ou pas?

[invite292e91f0]

-257+3*105=58

Or 58= 7*8+2 = 2 modulo 7
58= 5*11+3 = 3 modulo 5
58= 3*19+1 = 1 modulo 3

Donc il y a une erreur.
Je pense que c'est la formule du x qui est fausse... (si mes souvenirs sont bons...)

[A voir en vidéo sur Futura]

[sylvainc2]

x = 2 mod 3:

L'idée est de chercher un multiple des 2 autres moduli , ici 5*7=35, qui en même temps est congru à 2 mod 3, ie on cherche:
35k1 = 2 mod 3
La raison est que ce nombre, 35k1, est un multiple de 5 et de 7 donc il n'affecte pas les 2 autres congruences, il est 'neutre": 35k1=0 mod 5 et 35k1=0 mod 7.

Donc k1 = 35^-1 * 2 mod 3
= 2^-1 * 2 mod 3
= 2 *2 mod 3
= 1 mod 3
Donc u(1)=35*1 = 35

On fait la même chose pour les 2 autres congruences:
on cherche un multiple de 21 qui est congru à 3 mod 5:
21k2 = 3 mod 5
k2 = 21^-1 * 3 mod 5
= 1 * 3 mod 5
Donc u(2)=21*3 = 63

15k3 = 2 mod 7
k3 = 15^-1 * 2 mod 7
k3 = 1 * 2
donc u(3)=15*2 = 30

Alors x = 35+63+30 = 128 = 23 mod 105