Prove that if $d\mid\gcd(a,b)$, then $d\mid a$ and $d\mid b$. I saw this used in proving another theorem but it was not proved. Does anyone know how to prove it?

  • 1
    $\begingroup$ The slightly trickier part is the other way: if $d\mid a$ and $d\mid b$ then $d\mid \gcd(a,b)$. $\endgroup$ – Thomas Andrews Jul 9 '16 at 13:47
  • $\begingroup$ Hint: $\ d\mid c\mid a_1, a_2,\ldots\Rightarrow\, d\mid a_i\,$ by transitivity of the "divides" relation. In other words, this says that a divisor of a common divisor remains a common divisor. $\ $ $\endgroup$ – Bill Dubuque Jul 9 '16 at 13:56

Because $\gcd(a, b)$ is the greatest common divisor of $a$ and $b$, it is a common divisor of $a$ and $b$, so we get $\gcd(a, b) \mid a$ and $\gcd(a, b) \mid b.$

Now, if $d \mid \gcd(a, b)$, by the transivity of factors, we get $d \mid a$ and $d \mid b$.



$\gcd(a,b) | a $ and $\gcd(a,b) | b$

By transitivity of divisibility, $d | a$ and $d | b$.


Your Answer

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