Proof for: GCD and divisibility

Question

I need some hints how to proof something like the following:

Let $a,b \in \mathbb{Z}$ with $a,b \not= 0$ and let $\gcd(a,b)=d$.

(1) For any $m,n\in \mathbb{Z}$ we have $d \mid ma+nb$.

(2) There exist $t,r \in \mathbb{Z}$ so that $d = ta + rb$.

Thank you very much for any help ;)

Answer 1

$\textbf{Hints:}$

For (1), try to prove that $d$ divides both $ma$ and $nb$.

For (2), use the Euclidean algorithm to find $d$ and follow the algorithm in reverse direction to write $d$ as a linear combination of $a$ and $b$.

Answer 2

$(1)\,$ follows by basic divisibility laws: for any $\,d\in\Bbb Z\!:\ d\mid a,b\,\Rightarrow\, d\mid\,\color{#0a0}ma,\color{#0a0}nb\,\Rightarrow\,d\mid ma\color{#c00}+nb.\,$ Said equivalently, the set of multiples of $d$ are closed under integer $\rm\color{#0a0}{scalings}$, and under $\color{#c00}{\rm addition}$ (the same holds true for the set of common multiples of any set of integers). Or, for a direct proof: $\, a = \bar a d,\, b = \bar b d\, $ so $\, ma + nb = m\bar a d + n\bar b d = (m\bar a + n\bar b) d\,$ is a multiple of $d$.

This linear structure of a set of (common) multiples of an integer lies at the heart of many divisibility results. This innate linear structure is brought to the fore when one studies ideals in rings, as well as modules - a generalization of a vector space with scalarsfrom rings (vs. fields).

$(2)\,$ can be proved by (complete) induction, using the basic descent step of the Euclidean algorithm for the gcd, that the gcd remains the same if we subtract the smaller argument from the larger one, i.e $\ \gcd(a,b) = \gcd(a,b\!-\!a).\,$ If $\,0 < a < b\,$ then $\,a+(b\!-\!a) < a+b,\,$ so, by complete induction on the height $\,:= a+b\,$ of $\,\gcd(a,b),\,$ we conclude that $\,d = m a + n(b-a)\,$ for some $\,m,n\in\Bbb Z,\,$ But, rearranging, $\,d = (m-n)a + nb\,$ is also a linear combination of $\,a,b.\,$ QED $ $ That's a sketch of the inductive proof of the Bezout Identity for the gcd. You need to fill in details, e.g. base case(s).

Remark $\ $ Interpreted constructively, the above yields an extended Euclidean algorithm that computes the gcd linear Bezout representation. For efficiency we can replace the above subtractive descent by its iteration to modular form $\,\gcd(a,b) = \gcd(a,b\!-\!qa) = \gcd(b,\, b\ {\rm mod}\ a).$ If we annotate the remainder sequence with equations expressing each remainder as a linear rep of $\,a,b\,$ then we obtain a very simple extended gcd algorithm, which is conveniently expressed in terms of row operations (as in linear algebra). This is both easier and far less error-prone than the alternative method of back-substitution. See this post for complete details.