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".
 A: 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$). 


*

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

*If $e\mid a$ and $e\mid b$ then $e\mid c$.
1) and 2) are the definition of $\gcd(a,b)$.
A: This is Bézout's lemma/identity. 
See two proofs here
A: 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.
A: 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$.

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