Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


locked by arjafi May 8 '15 at 6:57

This question exists because it has historical significance, but it is not considered a good, on-topic question for this site, so please do not use it as evidence that you can ask similar questions here. This question and its answers are frozen and cannot be changed. More info: help center.

closed as off-topic by Jonas Meyer, pjs36, Chappers, graydad, Jeel Shah Apr 25 '15 at 2:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Jonas Meyer, pjs36, Chappers, graydad, Jeel Shah
If this question can be reworded to fit the rules in the help center, please edit the question.

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
up vote 11 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.


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

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

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


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