dm: le Theoreme de Bachet de Méziriac

[MArie TS]

Bonjour, j'ai cet exercice en devoir maison mais je me trouve bloquée pour cette partie:

soit a et b deux entiers naturels non nuls de l’ensemble E=(ax-by) avec x et y appartenant à Z

1. démontrer que E+ est non vide, en déduire qu'il admet un plus petit élément noté d, ainsi il existe deux entiers relatifs x0 et y0 tq: d=ax0-by0

2. demontrer que tout multiple de d est un element de E

3.soit N un element de E et r le reste de la division euclidienne de N par d. Demontrer que r est, comme N un element de E. L'entier N peut-il appartenir a E+? En deduire que r=0 et que N est multiple de d

4.En deduire que E est l’ensemble des multiples de d (noté dZ)

5. demontrer que a et b appartiennent a E. en deduire que d est un diviseur commun de a et b

6.Demontrer que si d' est un diviseur commun positif de a et b alors d' divise d et par suite d' est inferieur ou egal a d (indication:d=ax0--by0)

7. Qu'en deduis t-on sur d?

J'ai repondu à la 1. et la 2. mais je suis perdue pour le reste! Je n'ai aucune idée de ce que dois dire pour la question 3 et la suite sinon que je me doute que pour la question 7 d est le PGCD de a et b ... pouvez vous m'aider s'il vous plait?

[sos-math(27)]

Excusez moi, mais je ne saisis pas ce qui correspond à E+ ?

[sos-math(27)]

3.soit N un element de E et r le reste de la division euclidienne de N par d. Demontrer que r est, comme N un element de E. L'entier N peut-il appartenir a E+? En deduire que r=0 et que N est multiple de d

4.En deduire que E est l’ensemble des multiples de d (noté dZ)

Pour cette question il faut écrire et utiliser la division euclidienne de N par d.

[MArie TS]

E+ c'est l'ensemble des entiers de E strictements positifs

la division euclidienne de N par d est du type N=qd+r
si N est un element de E et r le reste alors r est aussi un element de E...
je ne suis pas sure que ce soit ça

[sos-math(27)]

Pourquoi r appartiendra à E ? (la réponseest simple en regardant l'égalité que vous venez d'écrire...

[MArie TS]

Ah comme on a cette egalitée, N=qd+r, N etant un element de E et r un element de N alors r est un element de E?

L'entier N peut-il appartenir a E+? En deduire que r=0 et que N est multiple de d

oui l'entier peut appartenir a E+ (je ne sais pas comment le justifier)

N est un multiple de d et il est element de E donc r=0 donc N=qd , N est bien multiple de d
c'est cela?

[sos-math(27)]

En fait il suffit de transposer : r= N - q x d = 1 x N + (-q) x d ; donc r s'écrit bien comme un élément de E !

Je vous laisse continuer ensuite, il faut toujours utiliser les propriétés de la division euclidienne, en particulier, sur la comparaison de r et d.
Supposez que N appartient à E+, et vous arriverez à une contradiction.

Je pense que le reste de l'exercice est accessible ensuite.
A bientôt

[MArie TS]

merci pour votre aide, j'ai essayer de faire la suite seule mais j'ai eu beaucoup de mal pourriez vous me corriger là ou il y a des erreurs svp?

3. r est donc un element de E. Supposons que N appartienne a E+, N est donc un entier strictement positif.
N= qd+r= q(ax0-by0)+r
=qax0-qby0+r*1
mais je ne vois pas comment on vois qu'il n'est pas strictement positif...

4. N est un element quelconque de E, et est multiple de d. Si N appartient a E et N=q*d alors tous les elements de E sont des multiples de d.
E est donc l'ensemble des multiples de d.

5. E=ax-by et d=ax0-by0
donc E=a(x0*z)-b(y0*z)
E=ax0*z-by0*z
E=z(ax0-by0)=z*d=q*d on a bien a et b qui sont des multiples de d donc a et b appartiennent a E

a et b sont tous deux multiples de de d d est donc un diviseur commun a a et b.

6. je suis vraiment bloquée sur cette question, j'ai esprimé E en fonction de d puis de a et b j'ai rajouté des inconnues... mais je n'y arrive pas.

7. Si on a d' inferieur ou egal a d et d' divise d, avec d un diviseur commun a a et b, alors d est le plus grand diviseur commun de a et de b. PGCD(a,b)=d

je pense que j'ai fais beaucoup d'erreur... pouvez-vous m'aider?

[sos-math(21)]

Bonjour,
il faut partir de ce qu'a dit mon collègue.
Si N est un élément de E, alors il peut s'écrire comme \(N=ax-by\), avec \(x\) et \(y\) entiers relatifs.
De même d est un élement de E : \(d=ax_0-by_0\)
et on a \(r=N-qd=ax-by-q(ax_0-by_0)=a(....)-b(....)\) : développe et factorise par a et b ce qui peut l'être ; cette écriture permettra de prouver que \(r\) est un élément de E.
Reprends cela

[MArie TS]

Ah ça y est!! j'ai compris!! j'arrive au final a demontrer que r appartient a E, et que N est un multiple de d.
dans ce cas (question 4.) tous les elements de E sont des multiples de d, mais comment montrer justement que E est l'ensemble des multiples de d?

[sos-math(21)]

Bonjour,
Tu as montré que les éléments de E sont multiples de \(d\).
Il te reste à montrer la réciproque, c'est-à-dire que tous les multiples de \(d\) sont dans E.
Pars donc d'un élément \(n=kd\), avec \(k\) entiers relatifs et montre que \(n\in E\).
Bon courage

[MArie TS]

Ah je comprend! merci!! je demontre que n appartient à E, et si un element quelconque multiple de d appartient a cet ensemble, c'est que E est l'ensemble des multiples de d!
Et pour demontrer la question suivante, que a et b appartiennent a E, il suffit de montrer qu'ils sont des multiples de d. Mais comment faire? je suis partie de l'expression de E de depart avec ax-by, mais mon developpement je montre que E = q*d, je ne comprend pas ce qui ne vas pas... ai-je bien la bonne methode?

[sos-math(21)]

Bonsoir,
pour montrer que \(a\) et \(b\) appartiennent à E, c'est très simple :
Pour \(a\) : \(a=a\times 1-b\times 0\), donc \(a\) est bien de la forme \(ax-by\), avec \(x\,,\, y\in \mathbb{Z}\) donc \(a\in E\)
Fais la même chose avec \(b\).
Bonne continuation

[MArie TS]

merci beaucoup!!

dans ce cas pour repondre a la question 6(Demontrer que si d' est un diviseur commun positif de a et b alors d' divise d et par suite d' est inferieur ou egal a d (indication:d=ax0-by0) )
j'ai donc d=ax0-by0 et d'=ax-by
on a donc d=a*k=b*k' on doir montrer que d' est du meme type mais comment faire svp?

[sos-math(21)]

Bonjour,
si d' est un diviseur commun de a et b, alors il divise
si \(d'|a\), alors \(d'|ax_0\)
si \(d'|b\), alors \(d'|by_0\)
donc au final \(d'|????-????\) donc \(d'|....\)
Je te laisse conclure.
Bon courage