How to show $a,b$ coprime to $n\Rightarrow ab$ coprime to $n$?

Question

Let $a,b,n$ be integers such that $\gcd(a,n)=\gcd(b,n)=1$. How to show that $\gcd(ab,n)=1$?

In other words, how to show that if two integers $a$ and $b$ each have no non-trivial common divisor with and integer $n$, then their product does no have a non-trivial common divisor with $n$ either.

This is a problem that is an exercise in my course.

Intuitively it seems plausible and it is easy to check in specific cases but how to give an actual proof is not obvious.

Answer 1

Hint $\rm\ \ (n,ab)\ =\ (n,nb,ab)\ =\ (n,\overbrace{(n,a)}^{\large 1}\:b)\ =\ (n,b)\ =\ 1\ $ using prior said GCD laws.

Such exercises are easy on applying the basic GCD laws that I mentioned in your prior questions, viz. the gcd associative, commutative, distributive and modular law $\rm\:(a,b+c\:a) = (a,b).\,$ In fact, to make such proofs more intuitive we can write $\rm\:gcd(a,b)\:$ as $\rm\:a\dot+ b\:$ and then use familiar arithmetic laws, e.g. see this proof of the GCD Freshman's Dream $\rm\:(a\:\dot+\: b)^n =\: a^n\: \dot+\: b^n\:.$

Said conceptually: invertibles ("units") $\!\bmod n,\,$ are closed under multiplication, clear by

$$\begin{align}\rm a_k^{-1}\cdots a_1^{-1}&\rm\:\!\times\:\! (a_1\cdots a_k) =1\\[.2em] \rm\Rightarrow\ \ a_k^{-1}\cdots a_1^{-1} &\rm = (a_1\cdots a_k)^{-1}\end{align}\qquad$$

More generally: $ $ if $\rm\,(a,k)=(b,n)=1\,$ then $\rm\,(ab,kn)=(a,n)(b,k)$.

Remark $ $ Also worth emphasis is that not only are proofs using GCD laws more general, they are also more efficient notationally, hence more easily comprehensible. As an example, below is a proof using the GCD laws, followed by a proof using the Bezout identity (from Gerry's answer).

$\begin{eqnarray} \qquad 1&=& &\rm(a\:,\ \ n)\ &\rm (b\:,\ \ n)&=&\rm\:(ab,\ &\rm n\:(a\:,\ &\rm b\:,\ &\rm n))\ \ =\ \ (ab,n) \\[.2em] 1&=&\rm &\rm (a\color{#c00}r\!\!+\!\!n\color{#c00}s)\:&\rm(b\color{#c00}t\!\!+\!\!n\color{#c00}u)&=&\rm\ \ ab\:(\color{#c00}{rt})\!\!+\!\!&\rm n\:(a\color{#c00}{ru}\!\!+\!\!&\rm b\color{#c00}{st}\!\!+\!\!&\rm n\color{#c00}{su})\ \ so\ \ (ab,n)=1 \end{eqnarray}$

Notice how the first proof using GCD laws avoids all the extraneous Bezout variables $\rm\:\color{#c00}{r,s,t,u}\:,\:$ which play no conceptual role but, rather, only serve to obfuscate the true essence of the matter. Further, without such noise obscuring our view, we can immediately see a natural generalization of the GCD-law based proof, namely

$$\rm\ (a,\ b,\ n)\ =\ 1\ \ \Rightarrow\ \ (ab,\:n)\ =\ (a,\ n)\:(b,\ n) $$

This quickly leads to various refinement-based views of unique factorizations, e.g. the Euclid-Euler Four Number Theorem (Vierzahlensatz) or, more generally, Schreier refinement and Riesz interpolation. See also Paul Cohn's excellent 1973 Monthly survey Unique Factorization Domains.

Answer 2

$\gcd(a,n)=1$ implies $ar+ns=1$ for some integers $r,s$. $\gcd(b,n)=1$ implies $bt+nu=1$ for some integers $t,u$. So $$1=(ar+ns)(bt+nu)=(ab)(rt)+(aru+sbt+snu)n$$ so $\gcd(ab,n)=1$.

Answer 3

Let $P(x)$ be the set of primes that divide $x$. Then $\gcd(a,n)=1$ iff $P(a)$ and $P(n)$ are disjoint. Since $P(ab)=P(a)\cup P(b)$ (*), $\gcd(a,n)=\gcd(b,n)=1$ implies that $P(ab)$ and $P(n)$ are disjoint, which means that $\gcd(ab,n)=1$.

(*) Here we use that if a prime divides $ab$ then it divides $a$ or $b$.