# Division problem with GCD

• Feb 3rd 2007, 07:47 PM
Division problem with GCD
Let r, s, and t be integers, and suppose gcd(r,s)=1, r|t, and s|t.

Prove rs|t.

My work so far:

I have attempted to use the definition of gcd and division to solve the problem.

There exist integers a,b,c,d such that ra + sb = 1, rc = t, and sd = t.

I can prove that t = r(rca)+s(brc), and t^2 = rs(cd), but I just can't get to the right answer.

Thank you.
• Feb 4th 2007, 02:47 AM
CaptainBlack
Quote:

Let r, s, and t be integers, and suppose gcd(r,s)=1, r|t, and s|t.

Prove rs|t.

My work so far:

I have attempted to use the definition of gcd and division to solve the problem.

There exist integers a,b,c,d such that ra + sb = 1, rc = t, and sd = t.

I can prove that t = r(rca)+s(brc), and t^2 = rs(cd), but I just can't get to the right answer.

Thank you.

As $r|t$, and $s|t$, each of the prime factors of $s$ and $t$ appear in the prime decomposition of $t$ with at least the multiplicity that they appear in the decompositions of $s$ and $t$.

But as $gcd(r,s)=1$ they share no prime factors, so all the prime factors of $rs$ appear in the prime decomposition of $t$ with at least the multiplicity that they appear in the prime decomposition of $rs$. Hence $rs|t$.

RonL
• Feb 4th 2007, 05:37 AM
ThePerfectHacker
Quote:

Let r, s, and t be integers, and suppose gcd(r,s)=1, r|t, and s|t.

Prove rs|t.

My work so far:

I have attempted to use the definition of gcd and division to solve the problem.

There exist integers a,b,c,d such that ra + sb = 1, rc = t, and sd = t.

I can prove that t = r(rca)+s(brc), and t^2 = rs(cd), but I just can't get to the right answer.

Let, $r,s,t$ be positive integers.
And we know that $\gcd(r,s)=1$
Thus, $ar+bs=1$ for some integers $a,b$.
We also know that $r|t \mbox{ and }s|t$.
Thus, $t=rk$ and $t=sj$ for some integers $s,j$.
In the equation, $ar+bs=1$ multiply through by $t$ to get,
$art+bst=t$
Now you problem was that you subsituted the wrong way.
Meaning you subsituted first equation into first $t$ value and second equation into second $t$ value. You should have swaped them,
$ar(sj)+bs(rk)=t$
$rs(aj+bk)=t$
Thus, we see that $rs | t$.

Note, my method is better than CaptainBlank's because my was proven for all positive integers. He only proven it for intergers above 2 (otherwise they have no prime power decomposition).
• Feb 4th 2007, 06:52 AM
CaptainBlack
Quote:

Originally Posted by ThePerfectHacker
Note, my method is better than CaptainBlank's because my was proven for all positive integers. He only proven it for intergers above 2 (otherwise they have no prime power decomposition).

Examine it more carefully, I think you will find it does cover the possibility that one or both or r and s are 1.

RonL
• Feb 4th 2007, 01:15 PM