Explain why gcd(a, b) = 1.

Question

If 1 = sa + tb, where a, b, st ∈ Z, explain why gcd(a, b) = 1.

 

 

Answer 1

If you assume  gcd(a,b) ≠ 1  then we can write  a=qn and b=qm  for some common factor q ( all values ∈ Z ).

 

Then you can write

1 = s(qn) + t(qm) 

1 = q[sn + tm]

Do you see how that leads to the answer?  

 

 

 

 

 

 

 

 

 

 

Hint:  What if you divide both sides by q.  How can  1/q be ∈ Z ?