Question

Is this a true statement? Given two non-zero integers a,b. If there exists integer x,y such that ax + by = 1, then gcd(a,b) = 1?

Answer 1

I believe it's true. But not sure. So here is my attempt.

Suppose not, that gcd(a,b) = c, for some positive integer c > 1. Then by definition, c | a and c|b. I.e cm = a and cn = b for some integer m,n. Substitute we have:
cmx + cny = 1
c (mx + ny) = 1.

This implies c | 1. But c > 1. Hence this is a contradiction. The only value that divide 1 is 1. So c = 1

Right?

Answer 2

Yeah, I think this is used for Euclid algorithm

Answer 3

I believe that is the converse (with more assumptions) of Bézout's identity

Answer 4

the converse of Bézout's identity is not true in general. But if we restrict a,b to be non-zero, then it's true. (provided that the proof above is correct)

Answer 5

I never had any confidence in the validity of my proof. Which is why I asked this question to see if any one agrees.

Answer 6

it's true, this is a special case of Bezout's identity

Answer 7

any integer combination of \(x,y\) must be a multiple of \(\gcd(x,y)\), so if you have a combination \(ax+by=1\) it follows that \(\gcd(x,y)\,|\, 1\) so \(\gcd(x,y)=1\)

Answer 8

@oldrin.bataku awesome! thank you :D

Answer 9

consider that if \(\gcd(x,y)=z\) then \(x=mz,y=nz\) so it follows that \(amz+bnz=z(am+bn)=1\) so \(z\,|\, 1\implies z=1\) since we restrict \(z\gt0\)