Proving that $a,n$ and $b, n$ relatively prime implies $ab,n$ relatively prime

Question

Question:

Suppose $a,b \in \Bbb N$, $\gcd (a,n) = \gcd(b,n) = 1$. The question is to prove or give a counterexample: $\gcd(ab,n) = 1$.

My Work:

This is what I have so far (for $\alpha, \beta, \gamma, \delta \in \Bbb Z$): \begin{align*} \gcd(a,n) = 1 \ &\Rightarrow 1 = \alpha a + \beta n\\ \gcd(b,n) = 1 \ &\Rightarrow 1 = \gamma b + \delta n \end{align*} Multiplying the top equation by $b$, and the bottom by $a$, I have $$ b + a = (\alpha + \gamma)ab + (\beta b + \delta a)n $$

Here is where I am stuck. I now know that you can write a linear combination of $ab, n$ in this form, where all coefficients are integers, but I think I may have gone down the wrong road in this proof in multiplying by $a,b$. Hints would be appreciated.

Answer 1

Let $a=2, b=4, n=5$ shows statement is false.

Answer 2

The following is an answer to the question in the title, using the technique that you tried to use. Of course the answer has nothing to do with the question in the body of the post.

Because $a$ and $n$ are relatively prime, there exist integers $q$ and $r$ such that $qa+rn=1$. Similarly, there exist integers $s$ and $t$ such that $sb+tn=1$. Rewrite these equations as $qa=1-rn$ and $sb=1-tn$. Multiply. We obtain $$(qa)(sb)=(1-rn)(1-tn).$$ Expand and rearrange a bit. We get $$(qs)ab+(r+t-rtn)n=1,$$ which shows that $ab$ and $n$ are relatively prime.

Answer 3

Here is another simple solution for the question in the title.

Suppose by contradiction that $ab$ and $n$ are not relatively prime. Then they have a common prime divisor $p$.

Then $p$ divides $n$, and it also divides $ab$, hence either $a$ or $b$. Contradiction.

Answer 4

Suppose $n=17$, I think you can try $a$ and $b$ less than 17 and coprime to 17, in fact because 17 is a prime ...

Answer 5

Hint $\ $ By Euclid's Lemma, the naturals coprime to $\rm\:n\:$ are closed under multiplication. But sets $\rm\:S\ne \{1\}$ of positive naturals closed under multiplication always have non-coprime elements, e.g. $\rm\:1\ne a\in S\:\Rightarrow\:a^2\in S,\:$ so $\rm\:(a,a^2) = a \ne 1.$

As for Euclid's Lemma (the question in the title), by Bezout's Lemma, the elements coprime to $\rm\,n\,$ are exactly the invertible elements mod $\rm\,n,\,$ and $ $ a product of invertibles is invertible, thus

$$\rm (a,n) = 1 = (b,n)\:\Rightarrow\:\exists\, \bar a,\bar b:\ a\bar a\equiv 1 \equiv b\bar b\,\ (mod\ n)\: \Rightarrow\ ab\ \bar a\bar b\equiv 1\,\ (mod\ n)\:\Rightarrow\: (ab,n) = 1 $$

Answer 6

Think in terms of the prime factorizations of $a,b$, and $n$. (It doesn’t matter whether you’ve proved unique factorization yet; this is just a way to approach the problem.) Let $A$ be the set of prime factors of $a$, $b$ the set of prime factors of $b$, and $N$ the set of prime factors of $n$. Your hypothesis is basically that $A\cap N=\varnothing=B\cap N$, and the question is whether this imlies that $A\cap B=\varnothing$. When you put the question this way, the answer is pretty easy to see: the fact that $A$ and $B$ are both disjoint from $N$ says nothing at all about whether $A$ and $B$ overlap. Indeed, if $A=B\ne\varnothing$ it’s automatic that $A$ and $B$ will overlap. This immediately points you towards a counterexample like i.m. soloveichik’s. It actually gives you an even simpler one: just let $a=b=2$ and $n=1$!