# divisibility and gcd

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)

Thanks!

-

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.

-

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.

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$.