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.

$\gcd(a, b)$ should have the form of $ma+nb$, where $m,n\in\mathbb{Z}$, since $(a, b)$ divides both $a$ and $b$. But I dont know why it should be the smallest one which is positive.

share|improve this question
    
remember that $\gcd$ is unique up to units. You are in the ring of integer numbers, hence units are $1,-1$. So the positivity of $gcd$ is only a "choice" –  Federica Maggioni Apr 20 '13 at 15:24
add comment

3 Answers

The set $\rm\,S\,$ of positive integers of the form $\rm\:ma+nb\:$ is closed under positive subtraction, i.e. if $\rm\: j,k\in S\:$ then $\rm\:j > k\:\Rightarrow\:j-k \in S.\:$ So, by a simple fundamental lemma, the least positive element $\rm\:d\in S\:$ divides every element of $\rm\:S.\:$ Thus $\rm\:a,b\in S\:\Rightarrow\: d\mid a,b,\:$ i.e. $\rm\:d\:$ is a common divisor of $\rm\:a,b.\:$ Conversely, $\rm\:c\mid a,b\:\Rightarrow\: c\mid d = ma + nb\:\Rightarrow\:c\le d,\:$ so $\rm\:d\:$ is the greatest common divisor (i.e. any common divisor $\rm\:d\:$ of $\rm\:a,b\:$ having linear form $\rm\:d = ma+nb\:$ is necessarily greatest).

Hence we see that Bezout's identity for the gcd is just a special case of said fundamental lemma. This lemma has widespread applications in elementary number theory. The key innate structure is clarified when one studies university algebra: ideals are principal in Euclidean domains (and ideal-theoretic structure is hidden everywhere in elementary number theory).

Remark: it is is easy to verify the claim that $\rm\,S\,$ is closed under (positive) subtraction:

$$\rm\begin{eqnarray} j\, =\, ma+nb\in S\\ \rm k\, =\, \hat m a + \hat n b\in S\end{eqnarray}\bigg\rbrace,\ \ \, j>k\ \ \Rightarrow\ \ j-k\, =\, (m-\hat m)\, a + (n-\hat n)\,b \in S$$

share|improve this answer
add comment

Every $ma+nb$ is a multiple of $\gcd(a,b)$, so also the smallest positive such number is a multiple.

share|improve this answer
    
Can you please amplify your answer with more details? –  Dwayne E. Pouiller Apr 6 at 5:54
add comment

From Bezout's identity we have that $\gcd(a,b)=sa+rb$ for some $r,s\in\mathbb Z$.
Also $\gcd(a,b)\mid a , \ \gcd(a,b)\mid b$ and therefore for any $n,m\in\mathbb Z$ with $ma+nb>0\Rightarrow ma+nb=k\cdot\gcd(a,b)$ for some $k\in\mathbb N$.
Since $sa+rb=1\cdot\gcd(a,b)$ it follows that $\gcd(a,b)$ is the smallest element of $\lbrace ma + nb : m, n\in\mathbb{Z}\text{ and }ma+nb>0\rbrace$.

share|improve this answer
    
Can you please amplify your answer with more details? By reason of $k \in \mathbb{N}$ , $k \ge 1$ thence $k = 1$ is the smallest k? –  Dwayne E. Pouiller Apr 6 at 5:57
    
@DwayneE.Pouiller See my edited answer. –  P.. Apr 13 at 14:22
add comment

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.