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?

  • 3
    $\begingroup$ Hint: u and v have to be relatively prime. $\endgroup$ – 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.