[Math] Understanding a proof that $\gcd(a, b) = 1$ if $sa + tb = 21$ and $ua + vb = 10$

discrete mathematicsdivisibilityelementary-number-theory

I am studying the solution to a problem:

Suppose $a, b, s, t, u, v$ are integers such that $sa + tb = 21$ and $ua + vb = 10$. Show that $\gcd(a; b) = 1$.

ANSWER

For any a; b that are in the set Z, we know that gcd(a; b) is the smallest positive integer that can be
expressed as an integer linear combination of a and b.

Suppose gcd(a; b) = d = Xa + Y b; 9X; Y 2 Z. Clearly the two equations given are
constant multiples of this equation:

21 = c1  d = (c1  X)a + (c1  Y )b = sa + tb
10 = c2  d = (c2  X)a + (c1  Y )b = ua + vb
d = gcd(10; 21) = 1

I don't quite understand that last step. How is exactly did the writer jump to $d = \gcd(10,21) = 1$ in order to prove the problem?

I understand that there must be a smallest positive integer written as a linear combination of $a$ and $b$. But how exactly did the writer relate the two statements 

21 = c1  d = (c1  X)a + (c1  Y )b = sa + tb
10 = c2  d = (c2  X)a + (c1  Y )b = ua + vb

in order to find $d = \gcd(10,21) = 1$. I am having trouble grasping that key step. Any help or advice would be great!

Best Answer

Using explicit Bezout identities obscures the essence of the matter. Since $\,d = \gcd(a,b)\,$ divides every integral linear combination of $\,a,b,\,$ we deduce that $\,d\mid 21,10,\,$ so $\,d\mid\gcd(21,10) = 1.$

The final inference can be deduced by either Bezout: $\,1 = \gcd(21,10) = 21 j + 10k\,$ for $\,j,k\in\Bbb Z,\,$ thus $\,d\mid 21,10\,\Rightarrow\,d\mid 1,\,$ or, better, it can be deduce immediately from the universal property of the gcd: $\,d\mid m,n\iff d\mid \gcd(m,n)$.

Related Question