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)

Question

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

Answer 1

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