# Why does $\gcd(a, b) = \min\lbrace ma + nb : m, n\in\mathbb{Z}\text{ and }ma+nb>0\rbrace$?

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

-
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

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

-

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

-
Can you please amplify your answer with more details? – Dwayne E. Pouiller Apr 6 '14 at 5:54

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

-
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 '14 at 5:57
@DwayneE.Pouiller See my edited answer. – P.. Apr 13 '14 at 14:22
Thanks. Upvote. – Dwayne E. Pouiller May 10 '14 at 22:05