# Math Help - gcd integer proof

1. ## gcd integer proof

Hi all,

Let a and b > 0 be integers. Show that there exist integers u and v such that u+v = a and gcd(u, v) = b, if and only if b|a.

2. Originally Posted by sirellwood
Hi all,

Let a and b > 0 be integers. Show that there exist integers u and v such that u+v = a and gcd(u, v) = b, if and only if b|a.
Problem: if $a\ \in\ \mathbb{Z},\ b\ \in\mathbb{N},$ show that

$u,\ v\ \exists\ \in\ \mathbb{Z},\ u+v = a,\ gcd(u, v) = b\ \Leftrightarrow\ b|a$

Solutin: First suppose that b|a and show the left direction:

Set u = b and v = a - b. Since a and b are natural numbers, u and v are both integers. Since b divides a, b also divides a-b, hence it divides both u and v, so gcd(u, v) > b. But gcd(u, v) cannot be > u, so gcd(u, v) < u = b. So b < gcd(u, v) < b, which means that gcd(u, v) = b. Also, u + v = b + a - b = a. So, if b|a, it does exist such u and v.

Now show the right direction:

gcd(u, v) = b, so b divides both u and v, hence also u + v, so it must divide a as well. So, if such u and v exist, b divides a.