Multiplication and Remainders

Today's question is a very nice question I found on Yahoo Answers. There was a trigonometry question I was planning for today, but this question is more unique (and besides that, this blog has already many trigonometry questions).

When an integer N is divided by D, it gives a remainder of 7. When N is multiplied by 5 and divided by D, it gives a remainder of 10. What is D?

At first, you may think "I need N to do that". Well, if you had N, the solution would be obvious. That's why we need some creative thinking to find what this number D is.

First, we know that D must be greater than 10. If a/b gives a remainder of m, then b must be greater than m (if you divide something by 7, you can't get a remainder of 8, since that means the result of division must be greater by 1).

Now, since N/D gives a remainder of 7:
N = xD + 7

Also, we know that 5N/D gives a remainder of 10:
5N = yD + 10

Where x and y are integers.

Now multiply the first equation by 5:
5N = 5xD + 35
And equate it to the second one:
5xD + 35 = yD + 10
yD - 5xD = 25
D(y - 5x) = 25
D = 25 / (y - 5x)

Since D must be an integer, 25 must be divided by one of its factors: 1, 5, or 25. However, dividing it by 25 or 5 will give 1 or 5, which is less than 10. For this reason, D must be 25.

You can now take any number for x and create N. For example, let's see what happens when x = 3:
N = 3*25 + 7
N = 75 + 7 = 82
N/25 = 3 with remainder 7 (not surprising, as we went from the definition backwards).

Now multiply this N by 5:
5N = 410
Divide by 25:
410 / 25 = 16 with remainder 10

Nice, isn't it?
Have a great week,
Nadav

nadavs