Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given $a$ and $b$ I am trying to find an informal proof that the divisors that $a$ and $b$ have in common are the divisors of the number $n$ such that $n = \gcd(a,b)$.

I think it is obvious that the set of divisors between $a$ and $b$ (let us call it $S$) can't have a number greater than $n$. And therefore $S$ should contain the set of divisors for $n$.

But what I can't figure out is: how do I know there aren't other numbers in between $1 ... n$ that don't divide $n$ but are in $S$? Can I have a hint please?

share|cite|improve this question
up vote 2 down vote accepted

HINT For any $a,b \in \mathbb{Z}$, there exists $x,y \in \mathbb{Z}$ such that $$ax + by = \gcd(a,b)$$

share|cite|improve this answer
Ok, so I think I get it: $\gcd(a,b)$ is the smallest linear combination solution. All divisors of $a$ and $b$ divide the linear combination. Therefore, the two sets of divisors are the same then? – Dair Nov 22 '12 at 18:25

The proof I have seen uses the following fact: if $d = gcd(a,b)$ then there exists $x, y \in \mathbb{Z}$ such that $d = xa + yb$. In fact $d$ is the smallest positive integer that can be expressed as a linear combination of $a,b$ in this way.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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