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:

  1. 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.

  1. 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.

  1. 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.

  • $\begingroup$ You know 1) That $\gcd(ab,m)=g$ must exist and $g|ab$ and $g|m$. ANd you have just proven that $(ab)x_0x_1+ (m)y_2 = 1$. And by 1.1p3 you know that therefore $g|(ab)x_0x_1 + (m)y_2=1$. ANd so we conclude $g|1$. Which means $g= 1$. $\endgroup$ – fleablood Nov 28 '19 at 16:15

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

| cite | improve this answer | |

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

| cite | improve this answer | |
  • $\begingroup$ I was just thinking that if gcd(a,b)=1 can be thought of as a linear combination, this would mean that all pairs of consecutive numbers are relatively prime? If this is right, is it true that consecutive numbers do not share any prime factors? $\endgroup$ – Richard K Yu Nov 27 '19 at 3:34
  • $\begingroup$ This is correct. Another way of seeing this is that if $p | a$, where $b=a+1$, then $b \cong 1$ (mod $p$), so p can’t be a factor of $b$, meaning $a$ and $b$ share no prime factors. (Or even non-1 factors) $\endgroup$ – Noah Caplinger Nov 27 '19 at 3:38
  • $\begingroup$ I agree that we usually think of this in terms of prime factorizations. The book may be unable to give that argument at this stage, because the argument needs the uniqueness of prime factorization (the fundamental theorem of arithmetic) to say that any prime factor of $ab$ must be a factor of $a$ or of $b$. $\endgroup$ – Andreas Blass Nov 27 '19 at 15:46
  • $\begingroup$ " If this is right, is it true that consecutive numbers do not share any prime factors?" Very much so. Suppose $g$, a natural number, divides $n$, an integer. Then $\frac ng = m$ an integer. Then $\frac {n+1}g = \frac gn + 1g = m +\frac 1g$. The only way for that to be an integer and $g$ to be a natural number is for $g=1$. So $\gcd(n,n+1)$ is always one.... But may I say I have never seen your argument $1 = (n+1)-n$ so $\gcd(n,n+1)=1$ via Bezout before. That is very observant $\endgroup$ – fleablood Nov 28 '19 at 16:21

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


| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.