# To prove a property of greatest common divisor

Suppose integer $d$ is the greatest common divisor of integer $a$ and $b$, how to prove, there exist whole number $r$ and $s$, so that $$d = r \cdot a + s \cdot b$$ ?

i know a proof in abstract algebra, hope to find a number theory proof?

for abstract algebra proof, it's in Michael Artin's book "Algebra".

-

An approach through elementary number-theory:
It suffices to prove this for relatively prime $a$ and $b$, so suppose this is so. Denote the set of integers $0\le k\le b$ which is relatively prime to $b$ by $\mathfrak B$. Then $a$ lies in the residue class of one of elements in $\mathfrak B$.
Define a map $\pi$ from $\mathfrak B$ into itself by sending $k\in \mathfrak B$ to the residue class of $ka$. If $k_1a\equiv k_2a\pmod b$, then, as $\gcd (a,b)=1$, $b\mid (k_1-k_2)$, so that $k_1=k_2$ (Here $k_1$ and $k_2$ are positive integers less than $b$.). Hence this map is injective. Since the set $\mathfrak B$ is finite, it follows that $\pi$ is also surjectie.
So there is some $k$ such that $ka\equiv 1\pmod b$. This means that there is some $l$ with $ka-1=lb$, i.e. $ka-lb=1$.
Barring mistakes. Thanks and regards then.

P.S. The reduction step is: Given $a, b$ with $\gcd(a,b)=d$, we know that $\gcd(\frac{a}{d},\frac{b}{d})=1$. So, if the relatively prime case has been settled, then there are $m$ and $n$ such that $m\frac{a}{d}+n\frac{b}{d}=1$, and hence $ma+nb=d$.

-
It avails of nothing but the principle that, if $a\mid bc$, while $\gcd(a,b)=1$, then $a\mid c$. –  awllower Mar 28 '13 at 11:51
actually what i was looking for is an easier solution, that is by euclidean algorithm. this is much more complex. but, it's more fun! :D thanks @awllower –  athos Apr 3 '13 at 7:51
@athos Glad to share with you this fun answer! :D –  awllower Apr 3 '13 at 11:02

Here is a number theoretic proof (I hope not the one you already know):

Let $c=r\cdot a+s\cdot b$ be the smallest positive integer such that can be written as a linear combination of $a$ and $b$ with integer coefficients (note that $\left\{x\cdot a+y\cdot b\in\mathbb N:x,y\in\mathbb Z\right\}\neq\emptyset$).

1. Divide $a$ by $c$ to obtain $a=k\cdot c+\lambda$ for some $0\leq \lambda<c$. Thus $\lambda=a-kc=\ldots\Rightarrow \lambda=0$ (by the definition of $c$ as the smallest positive ...). Therefore $c\mid a$. Similarly $c\mid b$.

2. If $e\mid a$ and $e\mid b$ then $e\mid c$.

1) and 2) are the definition of $\gcd(a,b)$.

-
thanks, this is the one similar to what i know. but thanks! –  athos Apr 3 '13 at 7:35

This is Bézout's lemma/identity.

See two proofs here

-
I think that the two proofs in tthe link are both the same thing: Euclidean algorithm. So maybe you could elaborate more upon the answer, instead of a link only? In any case, still thanks. :) –  awllower Mar 28 '13 at 12:09
thanks, i got it! what i was not aware of is the extended euclidean algorithm. –  athos Apr 3 '13 at 7:40

The Euclidean algorithm (see it on Wikipedia, http://en.wikipedia.org/wiki/Euclidean_algorithm), when applied backwards, says that

the GCD can be expressed as a sum of the two original numbers each multiplied by a positive or negative integer, e.g., 21 = [5 × 105] + [(−2) × 252].

If you want $r$ and $s$ positive, just sum (a multiple of) $rs$ to both addends.

-

You can use any textbook on Number Theory, e.g., H.Stark, An Introduction to Number Theory, Theorem 2.2.

-