# Prove that if $d\mid\gcd(a,b)$, then $d\mid a$ and $d\mid b$.

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?

• The slightly trickier part is the other way: if $d\mid a$ and $d\mid b$ then $d\mid \gcd(a,b)$. – Thomas Andrews Jul 9 '16 at 13:47
• 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. $\$ – 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$.