0
$\begingroup$

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.

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

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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$?

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

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.