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.

No, because the the proof of the Extended Euclidean algorithm relies on this fact. — Bernard, Nov 07 '15 at 20:34
See also: http://math.stackexchange.com/questions/671748/show-that-if-ar-bs-1-for-some-r-and-s-then-a-and-b-are-relatively — Martin Sleziak, Jan 30 '16 at 13:38

score 3 · Answer 1 · answered Nov 07 '15 at 20:33

3

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

answered Nov 07 '15 at 20:33

Bernard

175,478

score 1 · Accepted Answer · answered Nov 07 '15 at 20:33

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$.

score 1 · Answer 3 · answered Nov 07 '15 at 20:33

1

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

answered Nov 07 '15 at 20:33

user236182

13,324

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

3 Answers3

Linked