# If $d\mid nm$ and $\gcd(n, m)= 1$ then exist $d_1, \,d_2$ such that $d=d_1d_2$ and $d_1\mid n,\,d_2\mid m$ (without Fund. Theorem of Arit)

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

• $d_1 = \gcd(n,d)$? – Teresa Lisbon Aug 25 '20 at 6:31
• But it's only said that $n, m$ are co-prime ! – Spectre Aug 25 '20 at 6:55
• Oh.. I see...You must be right...... – Spectre Aug 25 '20 at 6:55
• 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. – DanielWainfleet Aug 25 '20 at 8:05
• @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) – 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$$.

Proof:

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

• Why do you say gcd(d1,d2) implies d = kd1d2? – Oheyav Hashim Aug 26 '20 at 1:03
• 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$. – Ramasamy Kandasamy Aug 26 '20 at 3:19