Inscription / Connexion Nouveau Sujet
Problème de PGCD
en pleines révisions, je bloque sur cette question tirée d'un
problème de spé:
Dans l'exercice en question, x et y désignent des entiers naturels
non nuls vérifiant x<y
S est l'ensemble des couples (x;y) tels que PGCD(x;y)= y-x
Montrer que (x;y) appartient à S si et seulement si il existe un entier naturel
k non nul tel que x=k(y-x) et y=(k+1)(y-x)
Si vous parveniez à m'éclairer ce serait vraiment gentil. merci
d'avance
Voila c'est pas faute d'avoir bataillé 
On a PGCD(x;y)=d
D'après le Th. de Bezout, il existe u et v appartenant à Z tels que :
u*x+v*y = d
Or x=k(y-x) et y=(k+1)*(y-x)
On remplace
u*k*(y-x)+v*(k+1)*(y-x) =d
<=> d = (y-x)(u*k+v*k+v)
Donc y-x divise d.
<=> d = a * (y-x) (a apparentant à Z).
On a juste simplifié en rajoutant une lettre a la place d'une expression.
Or comme d est le pgcd de x et de y, on peut dire que
x = d*x'
y = d*y' (avec x' et y' premiers entre eux).
On remplace d.
x = x' * a * (y-x) (1)
y = y' * a * (y-x) (2)
Si on fait (2)-(1) on a :
y-x = y'*a*(y-x)-x'*a*(y-x)
y-x = a*(y-x)*(y'-x')
<=>
1 = a*(x'-y')
La seule solution a cette équation dans N est
a=1 et x'-y' = 1
Comme a = 1
et que d = a*(y-x)
alors d = y-x
Donc (x;y) appartient à {S}.
Voila. Je pense que c'est juste mais s'il y a une erreur signalez
le moi. Si vous comprenez pas qqch aussi.
Mayhem
Sinon, plus simple mais a peu près pareil : le début est le même
:
On a PGCD(x;y)=d
D'après le Th. de Bezout, il existe u et v appartenant à Z tels que :
u*x+v*y = d
Or x=k(y-x) et y=(k+1)*(y-x)
On remplace
u*k*(y-x)+v*(k+1)*(y-x) =d
<=> d = (y-x)(u*k+v*k+v)
Donc y-x divise d.
<=> d = a * (y-x) (a apparentant à Z).
D'autre part,
x=dx'
y=dy' (x' et y' premier entre eux).
donc y-x=dy'-dx' = d(y'-x')
donc d divise y-x
or y-x divise d
donc forcément d=y-x
Annuler
connectez vous