Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
6  
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
1  
@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$ –  Zvpunry Aug 31 '12 at 22:16
add comment

6 Answers 6

up vote 4 down vote accepted

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

share|improve this answer
    
You could have $n=3$ too ... –  Mark Bennet Aug 31 '12 at 20:14
    
Well...this is embarrassing. Thanks! –  Zvpunry 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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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