Reasoning about Integers

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 
about this some more, please write back.

- Doctor Achilles, The Math Forum
  http://mathforum.org/dr.math/