# If $a\mid d$, $b\mid d$, $a=u\cdot\gcd(a, b)$ and $b=v\cdot\gcd(a, b)$, then there is an integer $r$ such that $d=ruv\cdot GCD(a, b)$

Suppose $a\mid d$, $b\mid d$, $a=u\cdot\gcd(a, b)$ and $b=v\cdot\gcd(a, b)$. Show that there is an integer $r$ such that $d=ruv\cdot \gcd(a, b)$

Here, $a, b, u, v$ and $d$ are also integers. I know that $\gcd(a, b) = ma + nb$ (from the extended Euclidean algorithm). So I started with the equations:

1) $a=u(ma + nb)$

2) $b=v(ma + nb)$

But unfortunately I can no longer proceed. How to approach the proof?

• Hint: u and v have to be relatively prime. – NickD Jul 16 '17 at 17:30

As $a\mid d$, $d = n\cdot u\cdot gcd(a,b)$ for some interger $n$, however $d$ is also divisible by $v\cdot gcd(a,b)$ and so $n\cdot u$ is divisible by $v$. However $u$ and $v$ are relatively prime as they cannot share a factor because this factor would be incorporated into $gcd(a,b)$. Therefore $n = rv$ for some integer r and therefore $d = ruv\cdot gcd(a,b)$.