Let $a,b,n$ be integers such that $\gcd(a,n)=\gcd(b,n)=1$. How to show that $\gcd(ab,n)=1$?

In other words, how to show that if two integers $a$ and $b$ each have no non-trivial common divisor with and integer $n$, then their product does no have a non-trivial common divisor with $n$ either.

This is a problem that is an exercise in my course.

Intuitively it seems plausible and it is easy to check in specific cases but how to give an actual proof is not obvious.

  • 13
    $\begingroup$ 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. $\endgroup$ – davidlowryduda Sep 5 '11 at 22:21
  • 2
    $\begingroup$ I expanded the post and reopened it (it had been locked for a long time). The result is a standard result that should be somewhere and it answered here in a detailed way. Given that OP does not exist anymore it seemed non problematic to edit it significantly. $\endgroup$ – quid May 1 '19 at 13:16
  • $\begingroup$ See also: If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$ $\endgroup$ – Martin Sleziak May 3 '19 at 21:50

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

  • $\begingroup$ My answer shows how eliminating the unnecessary Bezout identities both simplifies and generalizes the proof. $\endgroup$ – Bill Dubuque Sep 10 '11 at 23:37
  • 1
    $\begingroup$ @Bill, sure, but your answer also requires knowing what you call "the basic GCD laws", which themselves require proof. $\endgroup$ – 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$.


Suppose $gcd(ab, n)=r$, because of the property of gcd, \begin{equation} r\geqslant 1\tag{1} \end{equation} And there $\exists s, t\in \mathbb{N}$ s.t. $$ab = rs$$ $$n = rt$$ and hence, $$a=\frac{rs}{b}, n =rt$$ In the case of $b\mid s$:

There $\exists x\in \mathbb{N}$ s.t. $$s=xb$$ Hence, $ab = rs = rxb\rightarrow a =rx$ $$a=rx$$ $$n=rt$$ Hence, $r$ is a common divisor of $a$ and $n$ and it must be smaller than the greatest common divisor. Therefore, $$r\leqslant gcd(a,n)=1$$ Because of (1), $$r=1$$ In the case of $b\nmid s:$

Since $a=\frac{rs}{b}\in\mathbb{N} \rightarrow b\mid r$. There $\exists y\in \mathbb{N}$ s.t. $$r=yb$$ Hence, $$a=\frac{rs}{b}=sy$$ $$n=rt=tby$$ Hence, $y$ is a common divisor of $a$ and $n$. Similarly, $y\leqslant gcd(a,n) = 1\implies y = 1$ and $r =b$. \begin{align*} r &=gcd(r, rt)\\ &=gcd(b,n)\\ &=1 \end{align*} Therefore, in both cases: $r=1$ $$gcd(ab, n) = r = 1$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy