Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 42

Demo pgcd



  1. #1
    Universmaster

    Demo pgcd


    ------

    Bonjour,

    J'ai un problème sur un exo de spé maths, on me me donne:

    Montrer que

    dans notre cour on note PGCD(a;b): a ^ b

    a ^ b = 1
    (ac) ^ (bc) = c
    Donc d'après Bézout,
    (ac)x + (bc)y = c
    Et comme (ac) ^ (bc) = c, c = (ac)u + (bc)v
    donc (ac)x + (bc)y = (ac)u + (bc)v
    ça fait : (ac)x + (b)cy = (c)au + (b)cv
    Donc ac ^ b = c ^ b

    Est-ce bien rigoureux?

    Cordialement, Universmaster.

    -----
    "Dieu ne joue pas aux dés" [Albert Einstein]

  2. #2
    MiMoiMolette

    Re : Demo pgcd

    Plop,

    En attendant de t'aiguiller de la bonne manière (faut que je me souvienne comment faire :s), j'ai relevé quelques trucs qui ne vont pas...

    (ac) ^ (bc) = c
    Donc d'après Bézout,
    (ac)x + (bc)y = c
    Et comme (ac) ^ (bc) = c, c = (ac)u + (bc)v
    Sauf que c'est exactement la même chose...même propriété, même méthode.

    Rappelons que Bézout permet d'écrire qu'il existe u et v de Z tels que au+bv=pgcd(a,b), mais la réciproque n'est pas vraie (sauf pour le cas où le pgcd est = 1) !! i.e. si on a au+bv=x, alors x n'est pas forcément le pgcd de a et b.

    Ce que tu as fait ici :

    ça fait : (ac)x + (b)cy = (c)au + (b)cv
    Donc ac ^ b = c ^ b
    Donc, faux ^^
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  3. #3
    Universmaster

    Re : Demo pgcd

    Ok ok lol ^^ j'essaye autre chose alors
    "Dieu ne joue pas aux dés" [Albert Einstein]

  4. #4
    MiMoiMolette

    Re : Demo pgcd

    Question comme ça, as-tu déjà entendu parler du lemme de Gauss ? (a|bc et a et b premiers entre eux, alors a|c)

    Bon, je crois que j'ai une démonstration, il y a juste un point sur lequel je ne suis pas sûre du caractère "rigoureux"...
    Dernière modification par MiMoiMolette ; 08/12/2007 à 15h13.
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

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

    Re : Demo pgcd

    Bon, je vais essayer de t'y lancer...

    Soit d = pgcd(ac,b) et d'=pgcd(b,c)

    La finalité sera de démontrer que d|d' et d'|d. On pourra alors en déduire que d=d'.

    Une des deux parties est évidente.

    Ne pas oublier que si d est le pgcd de deux nombres x, y alors d|x et d|y. De plus, si f|x et f|y, alors f|d (et non pas f=d), ceci parce que f fait partie des diviseurs communs à x et y, mais on ne sait pas si c'est le plus grand.
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  7. #6
    Universmaster

    Re : Demo pgcd

    Oui oui j'connais le lemme de Gauss.
    Ok merci, j'vais essayer de me lancer... j'donne des nouvelles dès que j'trouve un truc ^^
    "Dieu ne joue pas aux dés" [Albert Einstein]

  8. #7
    GalaxieA440

    Re : Demo pgcd

    hello

    J'ai une proposition mais elle me semble un peu bancale...


     Cliquez pour afficher
    "Pursue the small utopias... nature, music, friendship, love" Kupferberg

  9. #8
    MiMoiMolette

    Re : Demo pgcd

    Plop,

    Ce qui me gêne dans ton truc, c'est "ac+b étant de la forme au+bv ---> (ac)^b divise a^b, donc (ac)^b divise 1, donc (ac)^b=1"

    Mais j'ai peut-être mal lu...ne voudriez vous pas renommer les pgcd plutôt que d'utiliser le symbole ^ ? Ce serait plus clair :/
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  10. #9
    Universmaster

    Re : Demo pgcd

    Dans ce cas, peut-on écrire tout simplement:

    pgcd(a,b)=1
    donc d'après bézout, il existe c et d dans Z tels que:
    ac + bd = 1

    on a (ac)*1 + b*d = 1

    Donc pgcd(ac,b) = 1

    de même, on a: c*a + b*d = 1

    Donc pgcd(c,b)=1

    Donc pgcd(c,b) = pgcd(ac,b)

    ...?
    "Dieu ne joue pas aux dés" [Albert Einstein]

  11. #10
    GalaxieA440

    Re : Demo pgcd

    ok : "ac+b étant de la forme au+bv ---> (ac)^b divise a^b, donc (ac)^b divise 1, donc (ac)^b=1"

    ac + b c'est bien a*(c) + b *1, or le pgcd de a et de b s'exprime au+bv d'après Bezout.

    Donc si d= (ac)^b et d'=b^c et D a^b

    d divise ac + b donc comme je l'explique si dessus : d divise D.

    Donc d divise 1 puisque a^b=1 dans les hypothèses

    Donc d=1

    Me tromps-je ?
    "Pursue the small utopias... nature, music, friendship, love" Kupferberg

  12. #11
    Universmaster

    Re : Demo pgcd

    La réciproque de Bézout est bien vraie?
    "Dieu ne joue pas aux dés" [Albert Einstein]

  13. #12
    MiMoiMolette

    Re : Demo pgcd

    Bon, je vais essayer d'expliquer, bien que ce ne soit pas très pédagogique de donner la solution comme ça. Le problème étant que je ne suis pas sûre non plus... Tu peux ne pas regarder...

    Soient d = pgcd(ac,b) et d'=pgcd(b,c)

    Première étape : d'|d

     Cliquez pour afficher


    Deuxième étape : d|d'

     Cliquez pour afficher
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  14. #13
    MiMoiMolette

    Re : Demo pgcd

    Citation Envoyé par Universmaster Voir le message
    Dans ce cas, peut-on écrire tout simplement:

    pgcd(a,b)=1
    donc d'après bézout, il existe c et d dans Z tels que:
    ac + bd = 1

    on a (ac)*1 + b*d = 1

    Donc pgcd(ac,b) = 1

    de même, on a: c*a + b*d = 1

    Donc pgcd(c,b)=1

    Donc pgcd(c,b) = pgcd(ac,b)

    ...?
    Ca y est, j'ai trouvé le problème.

    c est un nombre donné par l'énoncé. Ce n'est pas forcément un nombre qui intervient dans l'écriture de l'identité de Bézout pour a et b.
    C'est au niveau du passage à la phrase en gras que ça cloche
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  15. #14
    Universmaster

    Re : Demo pgcd

    Citation Envoyé par MiMoiMolette Voir le message
    le pgcd de b et c n'est pas forcément égal à 1.
    Bah pourtant on a: c*a + b*d = 1
    c'est bien (c)*a + (b)*d = 1 Donc d'après la réciproque de bézout, on a pgcd(b,c) = 1 nan?
    "Dieu ne joue pas aux dés" [Albert Einstein]

  16. #15
    MiMoiMolette

    Re : Demo pgcd

    Citation Envoyé par GalaxieA440 Voir le message
    ok : "ac+b étant de la forme au+bv ---> (ac)^b divise a^b, donc (ac)^b divise 1, donc (ac)^b=1"

    ac + b c'est bien a*(c) + b *1, or le pgcd de a et de b s'exprime au+bv d'après Bezout.

    Donc si d= (ac)^b et d'=b^c et D a^b

    d divise ac + b donc comme je l'explique si dessus : d divise D.

    Donc d divise 1 puisque a^b=1 dans les hypothèses

    Donc d=1

    Me tromps-je ?
    Même sushi. Le c n'est pas n'importe quel nombre, de même que u et v. On ne peut pas associer c à u ou v.

    Bézout énonce clairement : Si d est le pgcd de a et b, alors IL EXISTE u et v tels que au+bv=d.

    Ca ne veut pas dire que ce sont tous les u et v possibles, en particulier c dans vos démonstrations.
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  17. #16
    GalaxieA440

    Re : Demo pgcd

    Je suis aussi de cet avis, en fait c'est parce que je n'arrive pas à voir pourquoi il en serait autrement... mais quelque chose m'échapperait-il ?
    "Pursue the small utopias... nature, music, friendship, love" Kupferberg

  18. #17
    MiMoiMolette

    Re : Demo pgcd

    Citation Envoyé par Universmaster Voir le message
    Bah pourtant on a: c*a + b*d = 1
    c'est bien (c)*a + (b)*d = 1 Donc d'après la réciproque de bézout, on a pgcd(b,c) = 1 nan?
    Le problème se situe dans ton écriture de c*a+b*d=1.
    Tu n'as pas le droit d'utiliser c. e a priori oui, mais pas c, car c'est un nombre quelconque donné par l'énoncé. Pas un nombre qui permette d'écrire l'identité de Bézout pour a et b.
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  19. #18
    GalaxieA440

    Re : Demo pgcd

    a oui vrai...

    Bon je recommence quelque chose....
    "Pursue the small utopias... nature, music, friendship, love" Kupferberg

  20. #19
    MiMoiMolette

    Re : Demo pgcd

    Citation Envoyé par GalaxieA440 Voir le message
    Je suis aussi de cet avis, en fait c'est parce que je n'arrive pas à voir pourquoi il en serait autrement... mais quelque chose m'échapperait-il ?
    Lis ma démonstration si tu le veux. Il faut passer par le lemme de Gauss.

    J'ai essayé d'expliquer votre erreur, si ce n'est pas clair, redemandez-le moi, je ferai de mon mieux.
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  21. #20
    GalaxieA440

    Re : Demo pgcd

    j'essaye un bon coup avant de craquer et je repost si je trouve...

    Merci de l'aide
    "Pursue the small utopias... nature, music, friendship, love" Kupferberg

  22. #21
    Universmaster

    Re : Demo pgcd

    Ok pour c...

    Sinon ta démo n'est pas mal non plus
    "Dieu ne joue pas aux dés" [Albert Einstein]

  23. #22
    MiMoiMolette

    Re : Demo pgcd

    C'est la partie qui m'avait posé problème en fait...je ne l'ai trouvée qu'en essayant de poster la solution.

    Mais je pense que je n'aurais pas dû le faire, le résultat est que tu as eu une solution toute faite :s
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  24. #23
    Universmaster

    Re : Demo pgcd

    Certes,

    j'étais en train d'essayer de comprendre l'utilité du lemme de Gauss depuis le post ou tu me l'as suggérer..

     Cliquez pour afficher
    "Dieu ne joue pas aux dés" [Albert Einstein]

  25. #24
    MiMoiMolette

    Re : Demo pgcd

    Citation Envoyé par Universmaster Voir le message
    Certes,

    j'étais en train d'essayer de comprendre l'utilité du lemme de Gauss depuis le post ou tu me l'as suggérer..

     Cliquez pour afficher
    Je sais...c'était pas la partie la plus facile...

    Il existe peut-être une autre démonstration hein !

    Bonne chance pour la suite et encore désolée d'avoir mis à disposition la solution...


    L'heure d'aller se reposer...
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  26. #25
    Universmaster

    Re : Demo pgcd

    C'est vrai que après avoir tenté pendant plus de deux heures, la tentation est trop importante :s Mais c'est d'ma faute^^ j'peux m'en prendre qu'à moi, j'aurais pas dû :s En tout cas merci

    Bonne soirée,

    Cordialement, Universmaster.
    "Dieu ne joue pas aux dés" [Albert Einstein]

  27. #26
    GalaxieA440

    Re : Demo pgcd

    bon alors

    j'ai montré :

     Cliquez pour afficher
    "Pursue the small utopias... nature, music, friendship, love" Kupferberg

  28. #27
    Hamb

    Re : Demo pgcd

    Bonjour,
    cette implication est elle vraie ?

    Si c'est le cas, alors il est possible de démontrer ton implication de manière beaucoup plus directe qu'en montrant que chacun des pgcd divise l'autre.

  29. #28
    Universmaster

    Re : Demo pgcd

    Je ne crois pas, car comme l'a dit MiMoiMolette, la réciproque du lemme de Bézout ne marche pas, sauf si d = 1

    Cordialement, Universmaster.
    "Dieu ne joue pas aux dés" [Albert Einstein]

  30. #29
    Hamb

    Re : Demo pgcd

    Je me disais bien que la réciproque demandait une condition supplémentaire, et après une petite recherche internet j'ai réussi a la retrouver.
    Donc il y a en effet une démonstration directe, il suffit de traduire d'=PGCD(b,c) grace à bézout, de traduire a et b premiers entre eux toujours grace à bézout, et de tenter de faire apparaitre une égalité de la forme :

    Ensuite, il faut démontrer que d' divise ac et b (c'est facile).
    On peut alors utiliser l'implication suivante pour conclure :

  31. #30
    Universmaster

    Re : Demo pgcd

    Euh.. tu peux développer? C'est pas très clair.
    "Dieu ne joue pas aux dés" [Albert Einstein]

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. Pgcd.
    Par Poussiquette89 dans le forum Mathématiques du collège et du lycée
    Réponses: 3
    Dernier message: 28/11/2007, 21h45
  2. Pgcd
    Par M I L A S dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 08/11/2007, 18h10
  3. Pgcd!
    Par maths_comme_maths dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 04/10/2007, 17h07
  4. Pgcd
    Par ludovic BOURGOIN dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 23/10/2006, 09h28
  5. PGCD : est-il possible de retrouver A et B en connaissant le PGCD, Q, et R ?
    Par frhs dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 31/05/2005, 18h54