# 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 \$\displaystyle r|t\$, and \$\displaystyle s|t\$, each of the prime factors of \$\displaystyle s\$ and \$\displaystyle t\$ appear in the prime decomposition of \$\displaystyle t\$ with at least the multiplicity that they appear in the decompositions of \$\displaystyle s\$ and \$\displaystyle t\$.

But as \$\displaystyle gcd(r,s)=1\$ they share no prime factors, so all the prime factors of \$\displaystyle rs\$ appear in the prime decomposition of \$\displaystyle t\$ with at least the multiplicity that they appear in the prime decomposition of \$\displaystyle rs\$. Hence \$\displaystyle 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, \$\displaystyle r,s,t\$ be positive integers.
And we know that \$\displaystyle \gcd(r,s)=1\$
Thus, \$\displaystyle ar+bs=1\$ for some integers \$\displaystyle a,b\$.
We also know that \$\displaystyle r|t \mbox{ and }s|t\$.
Thus, \$\displaystyle t=rk\$ and \$\displaystyle t=sj\$ for some integers \$\displaystyle s,j\$.
In the equation, \$\displaystyle ar+bs=1\$ multiply through by \$\displaystyle t\$ to get,
\$\displaystyle art+bst=t\$
Now you problem was that you subsituted the wrong way.
Meaning you subsituted first equation into first \$\displaystyle t\$ value and second equation into second \$\displaystyle t\$ value. You should have swaped them,
\$\displaystyle ar(sj)+bs(rk)=t\$
\$\displaystyle rs(aj+bk)=t\$
Thus, we see that \$\displaystyle 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