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.

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

I have a positive integer $g$ such that $g$ is the least linear combination of the integers a and b. I have shown $g$ | $h$ ( where $h$ is an arbitrary linear combination of a and b, thus g divides all other linear combinations of a and b. So if we say g | ra + $sb$, where $r,a,s,b$ are positive integers. Does $g$ divide $a$ and $b$? Could someone explain this to me? (This is part of the classic $\gcd(a, b)$ proof by the way if that helps anyone)


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

Usually one proves $\rm\:g\:|\:ra+sb\:$ for all integers $\rm\:r,s\:$ (vs. all positive integers). From that we deduce that $\rm\:g\:|\:a,b\:$ by taking $\rm\:r,s = 1,0\:$ and $\,0,1.\:$ Revisit your proof: it probably works for all integers. Below is one conceptual way to present such a proof.

Hint $\ $ The set $\rm\:S\:$ of integers of the form $\rm\:x\:a + y\:b,\ x,y\in \mathbb Z\:$ is closed under subtraction so, by the Lemma below, every $\rm\:n\in S\:$ is divisible by the least positive $\rm\:d\in S.\:$ Thus $\rm\:a,b\in S\:$ $\Rightarrow$ $\rm\:d\:|\:a,b,\:$ i.e. $\rm\:d\:$ is a common divisor of $\rm\:a,b,\:$ necessarily greatest, by $\rm\:c\:|\:a,b\:$ $\Rightarrow$ $\rm\:c\:|\: \hat x\:a+\hat y\:b = d\:$ $\Rightarrow$ $\rm\:c\le d.$

Lemma $\ \ $ If a nonempty set of positive integers $\rm\: S\:$ satisfies $\rm\ n > m\ \in\ S \ \Rightarrow\ \: n-m\ \in\ S$
then every element of $\rm\:S\:$ is a multiple of the least element $\rm\:m_{\:1} \in S\:.$

Proof $\ \: $ If not there is a least nonmultiple $\rm\:n\in S,$ contra $\rm\:n-m_{\:1}\! \in S\:$ is a nonmultiple of $\rm\:m_{\:1}.\ \ $

Remark $\ $ This linear representation of the the gcd is known as the Bezout identity for the gcd. It need not hold true in all domains where gcds exist, e.g. in the domain $\rm\:D = \mathbb Q[x,y]\:$ of polynomials in $\rm\:x,y\:$ with rational coefficients we have $\rm\:gcd(x,y) = 1\:$ but there are no $\rm\:f(x,y),\: g(x,y)\in D\:$ such that $\rm\:x\:f(x,y) + y\:g(x,y) = 1;\:$ indeed, if so, then evaluating at $\rm\:x = 0 = y\:$ yields $\:0 = 1.$

The fundamental lemma, interpreted procedurally, yields Euclid's classical algorithm to compute the gcd using repeated subtraction.

share|cite|improve this answer

Clearly $g$ need not divide either $a$ or $b$, because $g$ could be something ridiculously large and $a$ and $b$ could be quite small. Say for example $g= 117$, where $r = 67, s = 50, a=b=1$.

Perhaps you are looking at the part of the Euclidean division algorithm where we are trying to find the GCD of $a$ and $b$, and we construct a series of smaller and smaller integers with the same GCD. In this case the implication goes the other way: We suppose that $g$ divides $a$ and $b$, and from that we can conclude that $g$ must also divide $ra+sb$ for any integers $r$ and $s$—and note, they need not be positive.

If none of this is to the point, perhaps you could say more clearly what you are looking at and what you are trying to understand.

Added after question was edited

If $g$ divides all linear combinations $ra+sb$ of $a$ and $b$, then in particular it divides the one where $r=1$ and $s=0$, and also the one where $r=0$ and $s=1$.

share|cite|improve this answer
I think I can add some additional information that might be helpful I just thought of it. – CodeKingPlusPlus Sep 2 '12 at 3:46

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.