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

Système de congruences



  1. #1
    patatoïde

    Système de congruences

    Bonjour,

    Nous sommes en train de faire un exercice sur les congruences, mais on ne comprend pas la correction qu'on a (d'ailleurs, on ne comprend pas non plus comment résoudre l'exercice).

    Alors, on a :

    1243 ^ 1067 = 11 (paraît que ça peut servir )

    On doit trouver x tel que :



    Le premier réflexe serait d'utiliser le théorème chinois, mais 1243 et 1067 ne sont pas premiers entre eux.

    Dans la correction :
    Ils se ramènent au système
    (113*11=1243)

    avec x = 25 + 11y
    Mais d'où vient ce -1 ? (et le système, tant qu'on y est - ça, c'est la patate)

    [pour info : suite de la correction]
    y = 678 est une solution particulière.
    Et les autrse diffèrent par un multiple de 113*97=10961
    Les solutions du système initial sont donc x=7483+120571k (et d'où vient 7483 ?)


    Mici,



    La patate (qui crie "non") et la molette (qui va s'en prendre une)

    -----


  2. Publicité
  3. #2
    haruspice

    Re : Système de congruences

    Alors, je n'ai pas fait les calculs mais selon moi ce qu'il se passe c'est qu'on divise dans chanque congruence par le pgcd et alors :



    Alors là on trouve les inverses de 11 modulo 113 et modulo 97 on fait la multiplication par 25 et 14 modulo 113 et 97
    en posant tu te ramènes à l'utilisation tu théorème chinois car 113 et 97 sont premiers entre eux et tu as quelque chose de la forme :


    voilà bonne chance
    Plus près de 40 que de 0 ... fallait bien que ça arrive !!!

  4. #3
    MiMoiMolette

    Re : Système de congruences

    Salut,

    En fait, ce qui nous a gênés c'est que dans la correction, ils introduisent un y dont on ne comprend pas trop l'origine, puis certaines données nous semblent bizarres...

    Sinon, oui, il est sûrement possible de se ramener à un cas d'utilisation du théorème chinois.
    Comme inverse de 11 dans Z/113Z, je trouve -41, ce que je n'arrive toujours pas à expliquer par rapport à la correction
    De plus, a-t-on le droit de dire que y=x/11 dans les deux cas, alors que l'inverse de 11 dans Z/97Z n'est pas le même que dans Z/113Z ?
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  5. #4
    haruspice

    Re : Système de congruences

    Salut c'est vrai que la méthode utilisée dans la correction ne me semble pas être la plus naturelle pour trouver le -1 je présume qu'il s'agit de 14*(25*11)^(-1) mudulo 97....
    Je pense qu'on à le droit de poser y=x/11 comme je l'ai fait mais c'est sûr que là ce n'est plus le même que celui de votre corrigé !
    en fait
    et celà revient à
    et
    d'où en simplifiant pas 11 :
    et
    et donc en faisant le chemin inverse on retombe sur le système avec y.
    j'espère que la démo vous convient mais c'est vrai qu'on est en droit de se demander pourquoi on ne cherche pas l'inverse de 11 modulo 97 et 113 et qu'on le multiplie par x... je pense que les deux systèmes sont équivalents c'est juste qu'on le laisse sous cette forme pour se retrouver dans le cas d'application du théorème chinois !
    Si quelqu'un a une explication plus rigoureuse je suis preneur aussi !
    Plus près de 40 que de 0 ... fallait bien que ça arrive !!!

  6. #5
    homotopie

    Re : Système de congruences

    Citation Envoyé par patatoïde Voir le message
    On doit trouver x tel que :

    De manière générale, soit un système du type :


    avec p et q premiers entre eux (ou autrement dit dp^dq=d).
    On a en particulier x-a est un multiple de d
    et en particulier x-a et b-a sont congrus modulo d
    Donc b-a est un multiple de d (b-a=d.c) s'il existe une solution au système.
    Dans ce cas on peut poser x-a=dy, autrement dit x=a+dy
    Le système devient :


    Ce qui revient à



    En appliquant au système initial on a x-25=11y (x=25+11y)


    Ce qui revient à :


    ce qui se résoud par le théorème chinois : y=solution particulière (existe toujours)+113.97k
    y=678+10961.k
    x=25+11(678+10961.k)=(25+11.67 8)+11.10961.k
    x=7483+120571.k

  7. A voir en vidéo sur Futura
  8. #6
    MiMoiMolette

    Re : Système de congruences

    Bonsoir,

    Merci infiniment pour ton explication. Tout est beaucoup plus clair ! Serait-ce indiscret de te demander d'où tu tiens cette méthode ? Car aucun de nous deux ne l'avons vue en TD (encore moins en cours) et pourtant la correction sous-entendait qu'on la connaisse...

    Ah oui, un point qu'on ne comprend pas (peut-être sur le coup) :

    Citation Envoyé par homotopie Voir le message
    et en particulier x-a et b-a sont congrus modulo d
    Donc b-a est un multiple de d (b-a=d.c) s'il existe une solution au système.
    Comment peut-on dire que x-a et b-a sont congrus modulo d ?

    Edit : ah oui, je vois now...x-a est un multiple de d...


    Merci à haruspice également,
    Dernière modification par MiMoiMolette ; 16/12/2007 à 20h56.
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  9. Publicité
  10. #7
    homotopie

    Re : Système de congruences

    Citation Envoyé par MiMoiMolette Voir le message

    Comment peut-on dire que x-a et b-a sont congrus modulo d ?

    Edit : ah oui, je vois now...x-a est un multiple de d...
    Rien à voir avec le fait que x-a soit un multiple de d (on rapproche les deux résultats après)
    x-a est congru à b-a modulo d car x-a est congru à b-a modulo dq : [(x-a)-(b-a)]=truc x qd donc égal bazar x d avec bazar=truc x q.

    Citation Envoyé par MiMoiMolette
    Merci infiniment pour ton explication. Tout est beaucoup plus clair ! Serait-ce indiscret de te demander d'où tu tiens cette méthode ?
    Trop ancien pour que je m'en souvienne.

  11. #8
    MiMoiMolette

    Re : Système de congruences

    x-a est congru à b-a modulo d car x-a est congru à b-a modulo dq : [(x-a)-(b-a)]=truc x qd donc égal bazar x d
    En fait, on pourrait aussi dire que x-a congru à 0 mod pd, donc x-a multiple de d.

    x-a congru b-a mod qd => x-a = b-a + qdk
    x-a multiple de d, qdk multiple de d, donc b-a multiple de d

    Ca marcherait comme ça ?

    Oki en fait, je proposais ça parce que je n'avais pas bien saisi certaines choses. Now, ça va :P
    Re-édit : je suis repaumée...

    J'ai beaucoup de mal avec ce passage :

    en particulier x-a et b-a sont congrus modulo d
    Donc b-a est un multiple de d (b-a=d.c) s'il existe une solution au système.
    Dans ce cas on peut poser x-a=dy, autrement dit x=a+dy
    Parce que si j'écris que x-a et b-a sont congrus modulo d, mon premier réflexe est de dire que x-a est un multiple de d, et donc que b-a en est un ~
    Dernière modification par MiMoiMolette ; 17/12/2007 à 20h27.
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  12. #9
    homotopie

    Re : Système de congruences

    Citation Envoyé par MiMoiMolette Voir le message
    En fait, on pourrait aussi dire que x-a congru à 0 mod pd, donc x-a multiple de d.

    x-a congru b-a mod qd => x-a = b-a + qdk
    x-a multiple de d, qdk multiple de d, donc b-a multiple de d

    Ca marcherait comme ça ?
    Oui là tu as compris.

  13. #10
    MiMoiMolette

    Re : Système de congruences

    Pourrais-tu expliquer pourquoi tu dis d'abord que b-a est multiple de d, puis x-a l'est, s'il te plaît ?

    (suite à l'énième édit de mon post précédent :s)
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  14. #11
    homotopie

    Re : Système de congruences

    Citation Envoyé par MiMoiMolette Voir le message
    Pourrais-tu expliquer pourquoi tu dis d'abord que b-a est multiple de d, puis x-a l'est, s'il te plaît ?

    (suite à l'énième édit de mon post précédent :s)
    Dans la rédaction initiale je crois que x-a multiple de d arrive avant.
    Mais surtout, c'est que "b-a multiple de d" est une condition nécessaire à l'existence de solution(s). Ce n'est pas la peine de chercher "x" si on sait qu'il n'existe pas.

  15. #12
    MiMoiMolette

    Re : Système de congruences

    Ah ok, on allie les hypothèses aux conditions donc...

    C'est juste cette inversion de conclusion que je n'avais pas comprise.

    Encore merci !


    (now, faut que j'arrive à expliquer ça à une patate )
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  16. Publicité

Sur le même thème :

Discussions similaires

  1. 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
  2. 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
  3. Congruences ...
    Par Bleyblue dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 10/12/2005, 18h10
  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