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.

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

share|improve this question

5 Answers 5

up vote 1 down vote accepted

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

share|improve this answer
    
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)$.

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

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

share|improve this answer

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.

share|improve this answer

This is Bézout's lemma/identity.

See two proofs here

share|improve this answer
    
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

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.