Demo pgcd

[invite425270e0]

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.
-----

[invite1237a629]

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 ^^

[invite425270e0]

Ok ok lol ^^ j'essaye autre chose alors

[invite1237a629]

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

[A voir en vidéo sur Futura]

[invite1237a629]

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.

[invite425270e0]

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 ^^

[GalaxieA440]

hello

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

 Cliquez pour afficher

a^b=1 --> au+bv=1
(ac)^b=(ac)u'+bv'
c^b=cu"+bv"

(ac)^b divise ac et b, donc toute combinaison linéaire de ac et de b, donc (ac)^b divise ac + b (entre autre).

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

ensuite : c^b divise c et b, et donc c^b divise (c(a)+b(1)) entre autre

donc c^b divise (ac)^b

Donc si je ne me suis pas planté :

Si a^b=1 alors (ac)^b=b^c=1

(le fait que ce soit tout égal à un me laisse perplexe...)

[invite1237a629]

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 :/

[invite425270e0]

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)

...?

[GalaxieA440]

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 ?

[invite425270e0]

La réciproque de Bézout est bien vraie?

[invite1237a629]

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

d'|b et d'|c. Donc d'|ac.
Donc d'|ac et b. Donc d'|d.

Deuxième étape : d|d'

 Cliquez pour afficher

d|ac et d|b.
Or, a et b sont premiers entre eux.

Démonstration de : d|b => d et a premiers entre eux.
Par l'absurde.
Si d|b et d et a n'étaient pas premiers entre eux, alors d et a auraient un diviseur commun k.
Donc k|d. Or, d|b. Donc k|b.
Donc k est un facteur commun à a et b.
Absurde.
Donc d et a sont premiers entre eux.


On a donc d|ac et a et d premiers entre eux.
Utilisation du lemme de Gauss.
Donc d|c.
Or, d|b aussi.
Donc d divise le pgcd de b et c, d'


d|d' et d'|d => d = d'

[invite1237a629]

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

[invite425270e0]

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?

[invite1237a629]

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.

[GalaxieA440]

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 ?

[invite1237a629]

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.

[GalaxieA440]

a oui vrai...

Bon je recommence quelque chose....

[invite1237a629]

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.

[GalaxieA440]

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

Merci de l'aide

[invite425270e0]

Ok pour c...

Sinon ta démo n'est pas mal non plus

[invite1237a629]

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

[invite425270e0]

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

le problème c'est qu'on pense trop peu souvent aux démonstrations par l'absurde.. J'avais réussi à montrer la première partie, d'|d mais pas la seconde :s

[invite1237a629]

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

le problème c'est qu'on pense trop peu souvent aux démonstrations par l'absurde.. J'avais réussi à montrer la première partie, d'|d mais pas la seconde :s

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...

[invite425270e0]

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.

[GalaxieA440]

bon alors

j'ai montré :

 Cliquez pour afficher

d'/c et d'/b ---> d'/xc+yb donc d'/d (entre autre)...

Ensuite :

d/ac et d/b

l'idéal serait de d/c...
or je peux dire que d ne divise pa a puisque ça sous entendrait que d divise a et c, or d'apèrs les hypothèses : a^b=1...

donc si d/ac, sachant que d ne divise pas a, ce qui signifie que d^a=1, alors d'après Gauss d/c

donc d/c et d/b ---> d/x'c+y'c et donc d/d' entre autre...

donc d=d' ce qui concluerait éventuellement si je ne me suis pas trompé nottament quand j'affirme : "je peux dire que d ne divise pa a puisque ça sous entendrait que d divise a et c, or d'apèrs les hypothèses : a^b=1..."

[Hamb]

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.

[invite425270e0]

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.

[Hamb]

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 :

[invite425270e0]

Euh.. tu peux développer? C'est pas très clair.