Prove that ∀a, b, u, v ∈ Z − {0} ua + vb = 1 → gcd(a, b) = 1

Question

How can I prove this statement:

$\forall a,b,u,v \in \mathbb{Z} - \big\{{0\big\}}\hspace{0.7em}ua+vb=1 \rightarrow \gcd(a,b)=1$

I don't even really know how to start off.

Probably with Euclid's Extended GCD Algorithm?

Thanks in advance.

Answer 1

There is a theorem that states that the gcd of two numbers is the minimal (natural) linear combination of them. I.e., $$\gcd\left(m,n\right)=\min\left\{am+bn\in\mathbb{N}\middle|a,b\in\mathbb{Z}\right\}$$

Another way is to prove it by definition: show that if $d|a$ and $d|b$, then $d=\pm 1$.

Answer 2

Since $\gcd(a,b)\mid ua$ and $\gcd(a,b)\mid vb$, we get $\gcd(a,b)\mid ua+vb=1$.

Answer 3

Any common divisor of $a$ and $b$ is a divisor of $ua+vb$.