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

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.

• You question does not match your title. Should the question end $gcd(ab,n)=1$? – Kris Williams Aug 31 '12 at 20:18
• One of the points of this question is to stress that a number $g$ being the gcd of a set of numbers is usually a stronger requirement than being the gcd of any proper subset of them. – Kirk Boyer Aug 31 '12 at 20:23
• @jmi4 The first comment is correct. Does your question concern the statement in the title, or the different statement in the body? – Bill Dubuque Aug 31 '12 at 21:11
• Sorry everyone! The body is a typo. I mean the $\gcd(ab,n) = 1$ – Moderat Aug 31 '12 at 22:16
• – Martin Sleziak May 4 '17 at 4:04

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

• You could have $n=3$ too ... – Mark Bennet Aug 31 '12 at 20:14
• Well...this is embarrassing. Thanks! – Moderat Aug 31 '12 at 20:15
• @MarkBennet Or any odd. – i. m. soloveichik Aug 31 '12 at 20:15
• Indeed - I had your example first, and then I thought 3 was a lower number - and I put up a higher one in my answer simply as an invitation to think a bit about what the question meant. – Mark Bennet Aug 31 '12 at 20:19
• Am I having a moment of stupidity or isnt gcd$(8,5) = 1$, supporting the claim? – fretty Sep 1 '12 at 18:31

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.

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.

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

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

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