Système de congruences

[Ard3nt]

Bonjour à tous !

J'ai un système de congruence que je voudrais résoudre grace aux théorème des restes chinois mais le problème c'est que je ne suis qu'en terminale et si je demande çà a mon prof il va me demander pour qui je me prend

Je m'en remet donc à vous pour m'expliquer au mieux la méthode.

On a : n congru à 13 ( mod. 19 )
et : n congru à 6 (mod.12)

Dans ce système de congruence, en se servant du théorème des restes chinois ( vu sur le forum par hasard ) on peut résoudre le système en disant que :

PGCD ( 12 , 19 ) = 1 , d'après le théorème des restes chinois, on a :

n = u*12*13 + v*6*19 + k*12*19 avec u,v,k appartenant à Z.

Soit n = 156u + 114v + 228 .

PGCD(19,12) étant égal à 1, d'après le théorème de Bezout, il existe 2 entiers relatifs u et v tels que 19v+12u=1.

Après avoir poser et remonter l'algorithme d'Euclide, on obtient un couple (u,v)=(-5,8).

On a donc : n= 8 * 156 - 5 * 114 + 228k

n = 678 + 228 k

Or 678 = 2 * 228 + 222, on a donc :

n = 222 + 228k, ce qui nous donne l'ensemble des solutions du système.

Mais je n'ai pas bien compris pourquoi nous pouvions affirmer ce qui est en gras, par exemple, pourquoi les u et v trouvés sont-ils les mêmes ?

J'espère que vous voyez ce que je veux dire :s

Merci d'avance.
-----

[God's Breath]

Bonjour

Dans ce système de congruence, en se servant du théorème des restes chinois ( vu sur le forum par hasard ) on peut résoudre le système en disant que :

PGCD ( 12 , 19 ) = 1 , d'après le théorème des restes chinois, on a :

n = u*12*13 + v*6*19 + k*12*19 avec u,v,k appartenant à Z.

Soit n = 156u + 114v + 228 .

PGCD(19,12) étant égal à 1, d'après le théorème de Bezout, il existe 2 entiers relatifs u et v tels que 19v+12u=1.

Après avoir poser et remonter l'algorithme d'Euclide, on obtient un couple (u,v)=(-5,8).

Mais je n'ai pas bien compris pourquoi nous pouvions affirmer ce qui est en gras, par exemple, pourquoi les u et v trouvés sont-ils les mêmes ?

Parce que le théorème des restes chinois ne dit pas que les solutions sont les
avec , , quelconques appartenant à ,
mais que les solutions de cette forme avec un couple convenant dans la relation de Bezout entre 12 et 19, et quelconque dans .

On a : n congru à 13 ( mod. 19 )
et : n congru à 6 (mod.12)

Le plus simple est quand même :
.

Comme 12 et 19 sont premiers entre eux, leur ppcm est , et les solution sont les avec

[Ard3nt]

Merci beaucoup, en fin de compte en suivant la trame porposée dans l'exercice on utilise la même méthode que le théorème des reste chinois sauf qu'au lieu de le nommer, on le redémontre par l'exemple.

La méthode que tu m'a proposée est par contre assez surprenante, enfin, on a pas trop l'habitude de faire des trucs comme çà, et je trouve çà dommage ...

Merci beaucoup.

[God's Breath]

La méthode que tu m'a proposée est par contre assez surprenante, enfin, on a pas trop l'habitude de faire des trucs comme çà, et je trouve çà dommage

La méthode que j'ai proposée n'a rien de surprenant, c'est toujours la même chose dans les problèmes linéaires, on trouve une solution particulière, ici , on la soustrait, et on résout le problème homogène associé.

Je reviens sur le théorème des restes chinois.
J'ai à résoudre le système de congruences ; si j'en connais une solution particulière , je le réécris immédiatement , ou encore , qui est équivalent à par définition même du ppcm.
Les solutions sont donc les avec .

Reste à trouver une solution particulière ...

Dans ton exercice, un peu d'habitude m'a fait remarquer que le système était conçu de telle sorte que et j'ai "vu" la solution particulière .

Dans le cas général, le théorème des restes chinois permet de calculer algorithmiquement une solution particulière .

Lorsque et sont premiers entre eux, on détermine par l'algorithme d'Euclide, une relation de Bezout entre eux : .
On pose et , et l'on a :
, , , .
Donc est une solution particulière du système.

Si tu regroupes le tout, tu vois que les solutions sont les
(car du fait qu'ils sont premiers entre eux), avec quelconque, mais que et proviennent, eux, de l'égalité de Bezout entre et , et ne sont pas quelconques.

[A voir en vidéo sur Futura]

[Ard3nt]

Merci de toutes ces précisions et aides, je vais surment bosser seul le théorème des restes chinois et m'habituer à ces méthodes.

Par contre, le bac approchant, croyez vous que si lors de l'épreuve j'ai à faire a un système, je peux me servir du théorème chinois ou alors cela donnerai -t-il une impression de " je veux sauter les étapes et je suis un gros casse cou " ?

[God's Breath]

Par contre, le bac approchant, croyez vous que si lors de l'épreuve j'ai à faire a un système, je peux me servir du théorème chinois ou alors cela donnerai -t-il une impression de " je veux sauter les étapes et je suis un gros casse cou " ?

Je n'ai aucune connaissance de l'esprit dans lequel est corrigé le bac à l'heure actuelle.