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.

Let $\gcd(a,n)=\gcd(b,n)=1$. How to show that $\gcd(ab,n)=1$? This is a problem that is an exercise in my course.

share|improve this question
9  
I am going to attempt to circumvent some of the other potential answerers - This is one of several number theory exercises that you have asked without showing your work. Since the ideas used here are exactly the same in your last question, I give you the HINT that you should use those answers, i.e. read them, comprehend them, and then apply them here. When you have progress to show or get stuck at a step, let us know. –  mixedmath Sep 5 '11 at 22:21

3 Answers 3

up vote 10 down vote accepted

HINT $\rm\ \ (n,ab)\ =\ (n,nb,ab)\ =\ (n,(n,a)\: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 associative, commutative, distributive and modular law $\rm\:(a,b+c\:a) = (a,b)\:.$ In fact, to make such proofs more intuitive one can write $\rm\:gcd(a,b)\:$ as $\rm\:a\dot+ b\:$ and then use familar arithmetic laws, e.g. see this proof of the GCD Freshman's Dream $\rm\:(a\:\dot+\: b)^n =\: a^n\: \dot+\: b^n\:.$

NOTE $\ $ 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) \\ 1&=&\rm &\rm (ar\!\!+\!\!ns)\:&\rm(bt\!\!+\!\!nu)&=&\rm\ \ ab\:(rt)\!\!+\!\!&\rm n\:(aru\!\!+\!\!&\rm bst\!\!+\!\!&\rm nsu)\ \ so\ \ (ab,n)=1 \end{eqnarray}$

Notice how the first proof using GCD laws avoids all the extraneous Bezout variables $\rm\: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.

share|improve this answer

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

share|improve this answer
    
My answer shows how eliminating the unnecessary Bezout identities both simplifies and generalizes the proof. –  Bill Dubuque Sep 10 '11 at 23:37
    
@Bill, sure, but your answer also requires knowing what you call "the basic GCD laws", which themselves require proof. –  Gerry Myerson Sep 11 '11 at 0:02
    
Sure, but the proofs of the "basic GCD laws" are all one-line trivial proofs - see my links. The small effort invested in proving these GCD laws quickly yields large benefits. To ignore these basic laws is akin to calculating limits without knowledge of derivative rules, MVT, l'Hospital, Taylor series, etc. Without such, one can still calculate some limits in ad-hoc ways. But doing so without such basic theory is so inefficient that it is painful. –  Bill Dubuque Sep 12 '11 at 15:07
    
@Bill, logically and pedagogically, limits are usually introduced before derivatives, MVT, etc., so students need to know the ad-hoc, inefficient ways. I think that applies to these gcd problems as well. –  Gerry Myerson Sep 12 '11 at 22:53
1  
I don't disagree with your statement, I just shift the emphasis from always to later. I champion answering questions in terms the person asking the questions can understand. –  Gerry Myerson Sep 13 '11 at 2:12

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

share|improve this answer

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.