# How to prove the divisors of two numbers is the same as the divisors of a and b?

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?

-

HINT For any $a,b \in \mathbb{Z}$, there exists $x,y \in \mathbb{Z}$ such that $$ax + by = \gcd(a,b)$$
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.