How to prove that $\gcd(m,n) = xm+yn$?

Question

I have just begun learning about algebraic structures and factorisation and have seen the following statement:

Given that integers $m$ and $n$ are not both $0$. There exist integers $x,y$ such that $\gcd(m,n) = xm+yn$

I am not quite sure what a proof to this statement would look like, nor have I been able to find one. I would greatly appreciate if someone knows the proof to this statement that they could perhaps show me what it looks like or where to find it.

Thank you in advance!

Answer 1

Without loss of generality, we can assume $\mathrm{gcd}(m,n)=1$. Consider the set $$S=\left \{1,1-m,1-2m,...,1-(n-1)m \right \}.$$ For $0 \leq i \neq j \leq n-1$ we can prove that $1-im \not\equiv 1 - jm \ (\mathrm{mod} \ n)$ (here we used the assumption $(m,n)=1$) and because $\left |S \right|=n$, exactly one element of $S$ must be divided by $n$, as desired.

More modern approach. $\mathbb{Z}$ is an Euclidean domain and hence a PID, the ideal $(m,n)$ generated by $m,n$ is principal, says, generated by some integer $d >0$ which can be taken as a definition of the greatest common divisor.

Answer 2

I would greatly appreciate if someone knows... where to find it.

You can find it in the references below.

• Theorem 0.2 in Gallian's book.
• Theorem 3.5 in Koshy's book.