If $h|mn$ and $\gcd(m, n)=1$ then $h=dd^\prime$ where $d|m$ and $d^\prime|n$

Question

Assume $m, n \in \mathbb{N}$.

I need to show the theorem in the title as a step in a larger proof about Euler's $\phi$ function.

My steps:

I divided it up to 2 cases:

If $\gcd(h, m) = 1$: Then $h|n$ and $h = 1\times h$.

If $\gcd(h, m) = x > 1$: Mark $h = \alpha x$. We know that $\gcd(x, n) = 1$ because if they share a factor $a > 1$ we get $a|x|m, a|n \Rightarrow $ contradiction to $\gcd(m, n) = 1$.

From here I can quite easily show it using prime decomposition, but I spent a long time searching for a more elegant way to proceed, without using the Fundamental Theorem of Arithmetic. Can you think of such a way? And if so, can you give me a hint for it?

Thank you all in advance :)

Answer 1

Hint:  let $d = \gcd(h,m)$ so that $h=d d'$ and $m=dm'$ for integers $d',m'$ with $\gcd(d',m')=1\,$. Then $h \mid mn \iff dd' \mid dm'n \iff d' \mid m'n\,$, but $\,d' \mid m'n \,\land\, \gcd(d',m')=1 \implies d' \mid n\,$.

Note that the hypothesis $\gcd(m,n)=1$ is not used, or necessary.

Answer 2

Eventually I figured out a proof without using the Fundamental Theorem of Arithmetic:

Denote $\gcd(m, \alpha ) = u$. $u|m \Rightarrow \gcd(u, n)=1$. $u|\alpha \Rightarrow \alpha = \beta u$.

Now since $\gcd(u, n) = 1$ and $\gcd(x, n) = 1$ we get $\gcd(ux, n) = 1$, and therefore $ux|\beta ux = \alpha x = h|mn \Rightarrow ux|mn \Rightarrow ux|m, ux|h$. Since $x = \gcd(m, h)$ we get $ux|x$ and therefore $u = 1 \Rightarrow \gcd(m, \alpha ) = 1$. At last, we also know that $\alpha | \alpha x = h | mn \Rightarrow \alpha | mn \Rightarrow \alpha | n$ (Since $ \gcd(m, \alpha ) = 1$).

So in conclusion: $h = x \alpha$ where $x|m$ and $\alpha | n$