If $n,m \in \mathbb{N}$ then there are $c,d$ such that $cd = (m,n)$, $(c,d) = 1$ and $(m/c,n/d) = 1$.

Suppose that $m,n \in \mathbb{N}$. Using the fundamental theorem of arithmetic it is easy to show that there exist $c,d \in \mathbb{N}$ such that $(c,d) = 1$, $cd = (m,n)$ and $(\frac{m}{c},\frac{n}{d}) = 1$.

Is there any quick way to prove this without using the prime factorizations of $m$ and $n$, i.e. only the basic properties of the gcd, lcm, etc.?

Solution 1:

$c$ consists of all the prime powers in $(m,n)$ that have the same exponent as in $m$ ...

Yes, expensive factorization is not needed. We can compute $\,c\,$ efficiently by iterated gcds that cancel from $\,m\,$ all primes that occur to higher power than in $\,(m,n).\,$ These are exactly the primes in $\,m' = m/(m,n)\,$ and we can cancel them from $m$ by repeatedly cancelling any gcd it has with $\,m',\,$ yielding the solution $\ c = {\rm gdc}(m, m'),\ \ d = (m,n)/c,\ $ where

$\begin{align}&{\rm gdc}(x,y)\ :=\qquad \text{// greatest divisor of $\,x\,$ that is coprime to $\,y$}\\ &\quad {\rm if}\ \, \gcd(x,y) = 1\ \ {\rm then}\ \ x\\ &\quad {\rm else}\ \, {\rm gdc}(x/{\rm gcd}(x,y),\,y) \end{align}$