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

  • $\begingroup$ $\gcd(x, h) = x$, as $h = \alpha x$. I did meant $n$, the one from the title ($m, n \in \mathbb{N}$) $\endgroup$ – AsafHaas Jun 21 '17 at 21:23

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.

  • $\begingroup$ That is indeed an elegant proof! Thank you :) $\endgroup$ – AsafHaas Jun 21 '17 at 23:29
  • $\begingroup$ @AsafHaas Thanks. With the additional condition $\gcd(m,n)=1$ it could be proved in a similar way that the representation $h=dd'$ is unique (up to units). $\endgroup$ – dxiv Jun 21 '17 at 23:32
  • $\begingroup$ Yes, that I already proved, and why I had that hypothesis in the first place. Also, the hypothesis of \gcd(m, n) is necessary in other parts of the theorem I am trying to prove so I thought it might be necessary here as well. $\endgroup$ – AsafHaas Jun 21 '17 at 23:37

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$


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.