Number theory greatest common divisor proof?

Question

Given integers a and b, prove:

If there exists integers x and y for which ax+by = gcd (a,b), then gcd(x,y) = 1

Answer 1

Let m=gcd(a,b),a=m*s and b=m*t!
Then
ax+by=m
msx+mty=m
sx+ty=1
In above formula gcd(s,t)=1

Now suppose gcd(x,y)=n and n>1
and x=np,y=nq
then sx+ty=n(ps+qt)=1
It is contradiction!
so, gcd(x,y)=1

Answer 2

What you have said is true if and only if a and b are relatively prime. It is true in general that for any two integers, a and b, there exist integers x and y such that ax + by = gcd(a,b). The proof is to just apply the Euclidean algorithm to a and b, then rearrange into the linear combination form.

Answer 3

Let aX + bY = d Euclid's Algorithm
a = dX
b = dY Defintion of GCD
dX(X) + dY(Y) = d Substitution
dX^2 + dY^2 = d Simplify
X^2 + Y^2 = 1 Divide by D.

Xx + Yy = e Euclid's Algorithm
X= ex
Y= ey Definition of GCD
ex(x) + ey(y) = e Substitution
ex^2 + ey^2 = e Simplify
x^2 + y^2 = 1 Divide by e.

x^2 + y^2 = X^2 + Y^2 = 1 Identity
(eX)^2 + (eY)^2 = X^2 + Y^2 Substitution
e^2 * X^2 + e^2 * Y^2 = X^2 + Y^2 Therefore,
e^2 = 1 Identity
e = 1
QED

Answer 4

What you have mentioned is genuine if and on condition that a and b are extremely best. that's genuine regularly that for any 2 integers, a and b, there exist integers x and y such that ax + by skill of = gcd(a,b). The information is to purely prepare the Euclidean set of rules to a and b, then rearrange into the linear combination form.

Answer 5

Let g=gcd(x,y)
Divide both sides by g:
(a/g) x + (b/g) y =1
Since g is the gcd, it divides both a and b so a/g and b/g are integers.

By Bezout's Lemma, gcd(x,y)=1