We want to prove that if $d\mid nm$ and $\gcd(n,m)=1$ then $d=d_1d_2$ where $d_1\mid n$ and $d_2\mid m$ and $\gcd(d_1,d_2)=1$

We already proved it using Fundamental Theorem of Arithmethic. But we wonder if there is a way to prove it using only GCD basic theorems.

Our hints

If $d_1\mid n$ and $d_2\mid m$, then $d_1d_2\mid nm$

$(a\mid b \implies a\mid bc)$

If $d\mid nm$ then $d\mid \gcd(d,n) \gcd(d,m)$ (Properties)

$\gcd(d_1,d_2)\mid \gcd(n,m)$

  • 2
    $\begingroup$ $d_1 = \gcd(n,d)$? $\endgroup$ – Teresa Lisbon Aug 25 '20 at 6:31
  • $\begingroup$ But it's only said that $n, m$ are co-prime ! $\endgroup$ – Spectre Aug 25 '20 at 6:55
  • $\begingroup$ Oh.. I see...You must be right...... $\endgroup$ – Spectre Aug 25 '20 at 6:55
  • $\begingroup$ There are other algebraic structures that have non-unique prime decompositions, so some very specific properties of $\Bbb N$ or $\Bbb Z$ must be used. $\endgroup$ – DanielWainfleet Aug 25 '20 at 8:05
  • $\begingroup$ @OheyavHashim The answer below is not helpful? Note that it takes the same $d_1,d_2$ as I proposed ($n$ switched with $m$, but no other change) $\endgroup$ – Teresa Lisbon Aug 26 '20 at 4:05

We can use the following two facts:

Lemma 1:

Given $m,n \in \mathbb{N}$, if $gcd(m,n) = 1$, then there exists, $x,y \in \mathbb{N}$, such that $xm + yn = 1$

Lemma 2:

For, $m, n \in \mathbb{N}$, if there exists $x, y \in \mathbb{N}$, such that $xm + yn= 1$, then $gcd(m,n) = 1$.


Now we can show that if $d_1 = gcd(d,n)$ and $d_2 = gcd(d,m)$ then,

$gcd(d_1, d_2) = 1$ and $d = d_1 d_2$.

The proof is trivial if $d_1 = 1$ or $d_2 = 1$. So, I will assume, $d_1 > 1$ and $d_2 > 2$.

$d_1 | m \implies \exists q_1 \in \mathbb{N} \ni m = q_1d_1$.

Similarly, $d_2 | n \implies \exists q_2 \in \mathbb{N} \ni n = q_2d_2$

From Lemma-1, there exists $x,y \in \mathbb{N}$ such that,
$$(xq_1)d_1 + (yq_2)d_2 = 1$$

Therefore it follows from Lemma-2 that, $$gcd(d_1, d_2) = 1$$

This implies $d = kd_1d_2$.

Now, it is given, $d | mn \implies kd_1d_2 | q_1q_2d_1d_2 \implies k | q_1q_2$.

Since $d_1 = gcd(d,m)$ and $d_2 = gcd(d,n)$, we have $gcd(k,q_1) = 1$ and $gcd(k,q_2) = 1$.

This taken together with $k | q_1q_2$ implies $k = 1$.

This proves that $d = d_1d_2$.

  • $\begingroup$ Why do you say gcd(d1,d2) implies d = kd1d2? $\endgroup$ – Oheyav Hashim Aug 26 '20 at 1:03
  • $\begingroup$ By our assumption, $d_1 | d$, therefore $d = md_1$, for some $m \in \mathbb{N}$. Also, $d_2 | d \implies d_2 | md_1$. Since $gcd(d_2, d_1) = 1$, $d_2 | m$, which implies, $\exists k \in \mathbb{N} \ni m = kd_2$. This gives $d = kd_1d_2$. $\endgroup$ – Ramasamy Kandasamy Aug 26 '20 at 3:19

Your Answer

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

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