# Thread: Division problem with GCD

1. ## 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.

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

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

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

5. I guess both methods are just as good.

But I'm more familiar with the second one, but thank you both!!!

KK

P.S. PerfectHacker, have you by any chance figured out my post in Calculus? I been working on it, but I just can't get part a and part c to make sense. I finished the second problem btw, if you want me to show the works please let me know, well, I'm not sure if I got it right.

Thank you again!