Pgcd(a,b)=pgcd(a+b,m)

[Anonyme]

Bonjour,

m desige ppcm(a,b)
comment peut-on démontrer que

pgcd(a,b)=pgcd(a+b,m)

Merci beaucoup de vos réponses

[Anonyme]

SVP donnez moi au moins des indices

[becirj]

Bonsoir

Soit d le PGCD de a et b; On a donc a=da' et b=db' avec a' et b' premiers entre eux. On a alors m=da'b'.
Appelons d' le PGCD de (a+b) et m.

d divise a et b donc divise (a+b) et d divise m , c'est un diviseur commun à (a+b) et m, comme le plus petit diviseur commun à (a+b) et m est d', on en déduit que d' divise d.

Utilisons le théorème de Bézout : il existe 2 entiers relatifs u et v tels que :
u(a+b)+vm =d'.
En utilisant les relations du début, on a :
u(da'+db')+vda'b'=d' soit d(ua'+ub'+va'b')=d'.
Par conséquent d divise d'.

Résumons : d' divise d et d divise d' donc d=d'.

[Anonyme]

Merci beaucoup Becirj,

d divise a et b donc divise (a+b) et d divise m , c'est un diviseur commun à (a+b) et m, comme le plus petit diviseur commun à (a+b) et m est d', on en déduit que d' divise d.

Est ce qu'on peut dire ici que : d divise d' ? (ou bien le sens est important ?)

Merci

[becirj]

Excuse moi mais je crois que j'étais fatiguée et j'ai raconté des bétises. J'ai démontré 2 fois la même chose avec des méthodes différentes. Je reprends toute la démonstration

Avec les mêmes notations : d = PGCD(a,b) ; d' =PGCD(a+b,m)
a=da' , b=db' avec a' et b' premiers entre eux et m=da'b'.

d divise a et b donc d divise (a+b) et d divise m donc d est un diviseur commun à (a+b) et m. Comme d' est le plus grand diviseur commun à (a+b) et m, tout diviseur commun à (a+b) et m est un diviseur de d' donc c'est d qui divise d'.

a'+b' est premier avec a' car un diviseur D commun à (a'+b') et a' diviserait leur différence b', on aurait alors D divise a' et b' qui sont premiers entre eux donc D=1.
De même a'+b' est premier avec b'.
Par conséquent a'+b' est premier avec a'b'.
Ce qui se traduit en utilisant le théorème de Bézout par : il existe deux entiers relatifs u et v tels que :
u(a'+b')+va'b' =1
En multipliant les 2 membres de cette égalité par d :
ud(a'+b')+vda'b'=d soit u(da'+db')+v(da'b')=d ou encore u(a+b)+vm=d.
L'ensemble des entiers u(a+b) +vm est l'ensemble des multiples du PGCD de (a+b) et m donc d est un multiple de d' ou encore d' divise d

d divise d' et d' divise d donc d=d'