Exercice systeme d'equation aux congruences

[invite77420056]

Bonjour

voici mon systeme

S {x=5 (15) et x=4 (14)

J'ai chercher une relation de bézout entre 15 et 14 ce qui donne 15.1 + 14. (-1)=1 donc 15.1.4-14.5=-10
Donc la solution est S: x=-10 (14.15)


est ce correct?
-----

[chris-034]

Tout à fait; on a bien -10 = 5 +15*(-1) = 4 + 14*(-1) .

[invite77420056]

merci est ce que je peux utiliser la meme methode pour ce genre de systeme de la forme S:{ x=a (m) et x=b (n)

Exemples

S:{x=1(10) et x=5 (15)

une relation de bezout donne 1. (-4)+5.1=1 donc -40+75=25 donc les solutions sont x=25 (150)

Est ce exact?

[invite77420056]

Pardon c'est x=35 (150)

[A voir en vidéo sur Futura]

[invite77420056]

Ah non c'est bien x=25 (150)

[chris-034]

Non. D'abord, c'est 75-40=35 = 5+2*15, mais ce n'est pas un 1 modulo 10 .

Le système se traduit en l'équation diophantienne : 10*A + 15*B = 4 . Ici, le pgcd de 10 et 15 est 5, or 4 n'est pas multiple de 5, donc cette équation n'a pas de solution.

Généralement, on a : a*u + b*v = c . Si d est le pgcd de a et de b, alors il divise a et b (so evident) donc il divise c. A l'inverse, si d ne divise pas c, c'est que l'équation n' a pas de solutions.

[invite77420056]

Et pour finire j'ai le systeme suivant S:{x=17 (21) et x=2 (6)

Relation de bezout il n'existe pas d'entier r et s tel que r.21 + 6.s=1 donc le systeme n'admet pas de solution.est ce correct?

[AdelineJ]

Regarde le théorème des restes chinois : http://fr.wikipedia.org/wiki/Th%C3%A...iers_entre_eux

[chris-034]

Pas exactement, avec Bezout, le membre de droite correspond au pgcd des deux coefficients de l'équation.

Ici, pour passer à l'équation diophantienne, on égalise les deux égalités du système, ce qui donne :
17 - 21*Y = 2 + 6*X <=> 15 = 6*X + 21*Y
Le pgcd de 6 et 21 est 3, 15 est multiple de 3 donc du pgcd, ce qui entraîne que cette équation possède une solution, et donc que le système du départ admet des solutions.
Ceci dit, passer par là n'est pas à faire systématiquement, seulement si il y a un doute; il est utile de vérifier à la fin si la solution trouvée vérifie le système.


Le ppcm de 6 et 21 est 42, donc pour résoudre le système, je met les modulos à 42:
2X = 34 [42]
7X = 14 [42]

Il vient : X = 1*7X - 3*2X = 1*14 - 3*34 [42] = -88 [42] = 38 [42]

On a bien 38 = 2 + 6*6 = 17 + 21*1.

[invite77420056]

Est ce qu'on peut utiliser cette methode pour tous les systemes aux congruences? Si non quelle methode utiliser?

[chris-034]

Il n'y a pas vraiment une seule méthode, mais celle que j'expose ci-dessus a l'air de marcher jusque là pour moi.