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.
Best Answer
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$.