This question already has an answer here:

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 Hase Dec 14 '14 at 2:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ You can prove this by looking at the powers in the prime factorizations of these numbers. $\endgroup$ – Prometheus Dec 13 '14 at 10:43
  • 2
    $\begingroup$ What definition of gcd do you use? The one I use says that the gcd is the positive common divisor divisible by all the other common divisors, so your question is part of my definition. $\endgroup$ – Gerry Myerson Dec 13 '14 at 11:51
  • $\begingroup$ GCD is the common divisor of two integers which is greater than any other common divisor. $\endgroup$ – Hesam Dec 13 '14 at 13:03

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?

  • $\begingroup$ $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? $\endgroup$ – Hesam Dec 13 '14 at 10:52
  • $\begingroup$ 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. $\endgroup$ – Henrik Dec 13 '14 at 11:03

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