Understanding why gcd(a,m) = gcd(b,m) = 1 implies gcd(ab, m) = 1 So I am following a proof from the textbook An Introduction to the Theory of Numbers by Niven, Zuckerman, and Montgomery.
The proof is for the following proposition:
If gcd $(a,m)$ = gcd $(b,m) = 1$, then gcd$(ab,m) = 1$.
The steps of the proof are as follows:


*

*There exist integers $x_0, x_1, y_0, y_1$ such that $1 = ax_0 + my_0 = bx_1 +by_1$
This follows from the theorem that for gcd$(a,b) = g$, there exist linear combinations such that $ax_0 + by_0 = g$. So we represent each of the gcds as a linear combination.


*We write $(ax_0)(bx_1) = (1-my_0)(1-my_1)$. We then write this equation in the form $abx_0 + my_0$. Rearranging gives $abx_0x_1 +my_2 = 1$ where $y_2 = y_0+y_1-my_1y_0$.


This second step makes sense for me because it follows algebraically.


*In the last step, the book notes: "From the equation $abx_0x_1 +my_2 = 1$ we note, by part 3 of Theorem 1.1 that any common divisor of ab and m is a divisor of 1, and hence gcd $(ab,m)=1$".


Part 3 of Theorem 1.1 just states $ a\mid b$ and $a \mid c$ $\implies  a \mid (bx+cy)$ for $x, y$ in the set of integers
I do not understand how this part of the theorem relates to establishing the last step of the proof.
The way I understand the last step of the proof is that the form $abx_0x_1 +my_2 = 1$ implies that 1 is a common divisor for $ab$ and $m$. The gcd $(ab,m)$ must then be a divisor of 1. Since there are no smaller positive divisors of 1 for 1, this means that gcd $(ab,m) = 1$.
I need to confirm if my understanding is correct and how the textbook arrives at the proof.
 A: Apply Part 3 of Theorem 1.1 with $b,c,x,y$ replaced with $ab, m, x_0x_1,y_2$, repectively. It tells you that any common divisor of $ab$ and $m$ is also a divisor of $abx_0x_1+my_2$, i.e., a divisor of $1$.
A: Andreas gives a good explanation of how your textbook proves this fact, but I want to pipe in and say that this proof isn’t how we usually think of this result. 
Another way of saying $\text{gcd}(a,m)=1$ is that $a$ and $m$ share no prime factors. (You might not have gotten to prime factorization yet, but you should keep this in mind for when you do). Similarly, $b$ and $m$ share no prime factors.
Any prime factor of $ab$ must be a factor of $a$ or a factor of $b$, so cannot be a factor of $m$. Then, $ab$ and $m$ share no common factors, meaning $\text{gcd}(ab,m)=1$. 
A: By Bezout theorem,
$$\gcd(a,m)=1 \iff$$
$$ (\exists \lambda \in \Bbb Z)\;\; : \;\; \lambda a\equiv 1 \;\;[m]$$
$$\gcd(b,m)=1 \iff $$
$$(\exists \mu \in \Bbb Z)\;\;  :\;\; \mu b \equiv 1 \;\;[m]$$
the product gives
$$\lambda \mu a b \equiv 1\;\; [m]$$
thus
$$\gcd(ab,m)=1$$
