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

Solution 1:

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

Solution 2:

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.