Associated Topics || Dr. Math Home || Search Dr. Math

```Date: 10/06/2004 at 08:40:38
From: Kim
Subject: Algebra

When positive integers p and q are divided by an even positive integer
t, they have remainders 2 and t/2, respectively.  What is the
remainder when the product pq is divided by t?

I'm not sure where to start.  2 * t/2 = t.  Therefore, you are left
with t.  So t/t = 1, so the remainder is 0?

```

```
Date: 10/06/2004 at 15:25:20
From: Doctor Achilles
Subject: Re: Algebra

Hi Kim,

Thanks for writing to Dr. Math.

Your reasoning is correct: you will end up with remainder 0.

Here is how I proved it:

p/t gives you remainder 2.  That means that there is some other
integer "n" that you can multiply by t and then add 2 to get p.

n*t + 2 = p

q/t gives you remainder t/2.  Using the same reasoning, there is some
integer m such that:

m*t + t/2 = q

Also, a remainder is always an integer.  Therefore t/2 is an integer.
Therefore, t is even.

Now, we need to multiply p and q together:

p*q = (nt+2)(mt+2)

If we do this, we find that:

p*q = nmt^2 + 2mt + nt^2/2 + t

We can then factor "t" out of the answer:

p*q = t(nmt + 2m + nt/2 + 1)

If we divide both sides by t, we get:

pq/t = nmt + 2m + nt/2 + 1

We know from the problem that t, n, and m are integers.  That means
that nmt is an integer and 2m is an integer.

We also know that t is even.  That means that nt is even.  So nt/2 is
an integer.

So, pq/t gives us a sum of integers.  Therefore pq/t is an integer.
Therefore pq/t has no remainder.

Hope this helps.  If you have other questions or you'd like to talk

- Doctor Achilles, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search