Répondre à la discussion
Affichage des résultats 1 à 6 sur 6

Système de congruences



  1. #1
    Ard3nt

    Système de congruences

    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.

    -----


  2. Publicité
  3. #2
    God's Breath

    Re : Système de congruences

    Bonjour
    Citation Envoyé par Ard3nt Voir le message
    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 .

    Citation Envoyé par Ard3nt Voir le message
    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

  4. #3
    Ard3nt

    Re : Système de congruences

    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.

  5. #4
    God's Breath

    Re : Système de congruences

    Citation Envoyé par Ard3nt Voir le message
    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.

  6. #5
    Ard3nt

    Re : Système de congruences

    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 " ?

  7. A voir en vidéo sur Futura
  8. #6
    God's Breath

    Re : Système de congruences

    Citation Envoyé par Ard3nt Voir le message
    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.

  9. Publicité

Sur le même thème :

Discussions similaires

  1. Système de congruences
    Par patatoïde dans le forum Mathématiques du supérieur
    Réponses: 11
    Dernier message: 17/12/2007, 20h53
  2. Congruences
    Par MS.11 dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 02/12/2007, 12h05
  3. Congruences
    Par ptit Ben dans le forum Mathématiques du collège et du lycée
    Réponses: 3
    Dernier message: 09/10/2007, 19h03
  4. Congruences!
    Par Bahamut dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 18/10/2004, 18h36
  5. congruences
    Par Jhary dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 27/09/2004, 19h13