2
$\begingroup$

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?

2 Answers 2

2

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

  • 0
    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?2012-11-22
1

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.