Is this a true stat… - QuestionCove
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