Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

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|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? –  user667648 Nov 22 '12 at 18:25
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.