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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

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

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

share|cite|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 '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

Your Answer


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.