OpenStudy (anonymous):

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?

2 years ago
OpenStudy (anonymous):

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?

2 years ago
OpenStudy (anonymous):

Yeah, I think this is used for Euclid algorithm

2 years ago
OpenStudy (anonymous):

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

2 years ago
OpenStudy (anonymous):

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)

2 years ago
OpenStudy (anonymous):

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

2 years ago
OpenStudy (anonymous):

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

2 years ago
OpenStudy (anonymous):

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\)

2 years ago
OpenStudy (anonymous):

@oldrin.bataku awesome! thank you :D

2 years ago
OpenStudy (anonymous):

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\)

2 years ago