Thread: 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.

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 show that



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.