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.?
$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}&amp;{\rm gdc}(x,y)\ :=\qquad \text{// greatest divisor of $\,x\,$ that is coprime to $\,y$}\\
&amp;\quad {\rm if}\ \, \gcd(x,y) = 1\ \ {\rm then}\ \ x\\
&amp;\quad {\rm else}\ \, {\rm gdc}(x/{\rm gcd}(x,y),\,y)
\end{align}$
Let $d=(m,n)$ and $c=1$, so the statement is proved trivially