# Prove problem of Mathematical Reasoning

The gcd of two integers $a$ and $b$ (both not zero) can be described as the smallest positive integer of the form $am+bn$, where $m,n \in \Bbb Z$. Prove that every positive $x$ of the the form $x=am+bn (m,n \in \Bbb Z)$ is an integral multiple of $d$= gcd$(a,b)$, i.e., prove that $$\{x|x=am+bn \text{ for some }m,n \in \Bbb Z \}=\{ x|x=cd \text{ for some }c \in \Bbb Z \}$$ (Use the Division Algorithm)

• if $d=am+bn$ then $cd=cam+cbn$. For the other side it is enough to prove that $d|a$ and $d|b$. Commonly $gcd(a,b)$ is defined in such a way that it suffices these conditions. – drhab Oct 22 '13 at 17:55

Let $d=gcd(a,b)=am+bn$. Suppose $x=ap+bq$ where $p$ and $q$ are integers. If $x$ is not a multiple of $d$ then $x=cd+r$ where $c$ and $r$ are integers and $0<r<d$. Then, $r=a(p-cm)+b(q-cn)$ is less than gcd($a,b$) and contradicts definition of gcd.
This is actually what Bezout's Lemma states. It says that for a given integers $a$ and $b$, the equation:
$$ax + by = d$$
has an integer solution for $x,y$ iff the $d$ is a multiple of $(a,b)$. All values for $d$, i.e. all multiple of $(a,b)$ are called Bezout's coefficients for this equation. Also $d=(a,b)$ is the smallest possible value for which this equation has solution. Here's some details of the proof.