# Suppose $\gcd(a,b)=1$ and $c|ab$. Prove there exist integers $r$ and $s$ such that $c=rs, r|a, s|b$, and $\gcd(r,s)=1$

I have the following problem on greatest common divisors:

Suppose $\gcd(a,b)=1$ and $c|ab$. Prove there exist integers $r$ and $s$ such that $c=rs, r|a, s|b$, and $\gcd(r,s)=1$.

Attempt: Basically, up to this point I've tried a whole lot of algebraic manipulation. Since $\gcd(a,b)=1$ we have $1=ma+nb$, for some integers $m,n$. Also, $ab=kc$ for some integer $k$. We aim to show (to begin with) that $r|a$, that is, that $a = rp$, for some integer $p$. So basically, I've started with the equation $1=ma+nb$ and multiplied by $a, b, ab$ etc., and I just can't seem to be able to express $a$ in the form above. I then looked at some of the results on prime factorisation, but they don't seem to shed any light on the situation.

Any help or hints would be appreciated.

• You really don't have much choice. Let $r=\gcd(a,c)$. Show that this works. – Andrés E. Caicedo Jan 31 '18 at 14:58

Say $g=\gcd(a,c)$ then $c=gd$ and $a=gx$ (so $d$ and $x$ are relatively prime). So we get $$gd\mid gxb$$ and thus $d\mid xb$. But $x$ and $d$ are relatively prime so $d\mid b$ and thus $b=de$ for some $e$.
So put $r=g$ and $s=d$ and you are done.
Let $r=\gcd(a,c)$ and $s=\gcd(b,c)$. It's easy to check that since $a,b$ coprime, $r\mid a$ and $s\mid b$ then $r,s$ are coprime. Thus the lowest common multiple of $r$ and $s$ is $rs$. Since $c$ is a common multiple, $rs\mid c$.
Finally, we know $r=aw+cx$ and $s=by+cz$ for some integers $w,x,y,z$. Now $rs=abwy+acwz+bcxy+c^2xz$, and each of these terms is divisible by $c$. So also $c\mid rs$.
You could think of $a$ and $b$ in terms of their prime factorizations. gcd$(a,b)=1$ tells you that there are no common prime factors between them and $c|ab$ tells you $c$'s factorization is a "substring" of $ab$'s. What happens if you take for $r$ $a$'s factors in that substring and do the same for $s$ and $b$?
Hint: Let $r$ be the greatest divisor of $c$ which is prime with $b$ and let $s$ be the greatest divisor of $c$ which is prime with $a$. Prove that $c=rs$.