Prove problem of Mathematical Reasoning

Question

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)

Answer 1

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.

Answer 2

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.

You can read the proof that's in the link that I've posted it's quite simple.