# Greatest common divisor is divisible by every common divisor [duplicate]

Can anyone give a proof for the following elementary assertion without use of Bézout's theorem which says that The Greatest Common Divisor of two integers is an integer linear combination of them.

"Every common divisor of two integers divides their greatest common divisor."

I should mention that I do not want to use the definition of GCD with prime factorization.

## marked as duplicate by Gerry Myerson, Ilmari Karonen, Clayton, user98602, Aditya HaseDec 14 '14 at 2:28

Assume the you have two numbers $n$ and $m$, their greatest common divisor $g$ and a common divisor $c$ that doesn't divide $g$. What will $gc$ divide?
• $gc$ divides $gm$, $gn$, $cm$, $cn$ and also $mn$. Which one do you mean? and what can I deduce from that? Can you explain your idea? – Hesam Dec 13 '14 at 10:52
• What I hinted at is actually not true (sorry for that), you should look at the smallest common multiple of $g$ and $c$. That divides a few more numbers than those in your list. Maybe i will be helpful to consider how the unique factorisations into primes of $m$, $n$, $c$ and $g$ looks. – Henrik Dec 13 '14 at 11:03