# If $\gcd(m,n)=1$ and $q|mn$, then $\exists d,e$ such that $q=de$, $d|m$, $e|n$, $\gcd(d,e)=1$ and $\gcd(\frac{m}{d},\frac{n}{e})=1$.

Let $m,n\in\mathbb{N}$ with $\gcd(m,n)=1$ and $q\in\mathbb{N}$ such that $q|mn$. Then there exists $d,e\in\mathbb{N}$ such that $q=de$, $d|m$, $e|n$, $\gcd(d,e)=1$ and $\gcd(\frac{m}{d},\frac{n}{e})=1$.

I am trying to prove the above claim but can only go as far as this:

As $q\in\mathbb{N}$, then there exists $d,e\in\mathbb{N}$ such that $q=de$. As $q|mn$, then there exists $x\in\mathbb{N}$ such that $mn=qx$. But $q=de$, so $mn=x(de)$. Since $mn=d(ex)=e(dx)$, then $d|mn$ and $e|mn$.

I even don't know if I'm going about it the right way. Some help would be greatly appreciated thank you.

• Welcome to mathSE! Don't be afraid to make your title as long as necessary in order to communicate exactly what your question is. More descriptive titles are always better. – 6005 Oct 25 '15 at 17:10
• @6005 I was worried it'd be too long for the title. Thank you for the response and edit, I will bear that in mind in the future. – T. Goodridge Oct 25 '15 at 17:17

Let $d=\gcd(q,m),\, e=\gcd(q,n)$. Because $\gcd(m,n)=1$, we get $de=\gcd(q,mn)$; and because $q\mid mn$, we get $\gcd(q,mn)=q$. Therefore $de=q$. Also $d\mid m,\, e\mid n,\, \gcd(d,e)=1$, as wanted.
$\gcd\left(\frac{m}{d},\frac{n}{e}\right)=1$ is unnecessary to consider: $\gcd(m,n)=1$ already implies it.
• To prove $de = q$, first show that $\gcd(m,q) \cdot \gcd(n,q) = \gcd(mn,q)$, since $m,n$ relatively prime. Then argue that $\gcd(mn,q) = q$.
• $d | m$ and $e | n$ are immediate.
• To prove $\gcd(d,e) = 1$, and $\gcd(\frac{m}{e}, \frac{n}{d}) = 1$, you can prove more generally that if $a$ divides $A$ and $b$ divides $B$ then $\gcd(a,b)$ divides $\gcd(A,B)$. Then take $A = m$ and $B = n$.