Without performing the actual division, determine the remainder when 742770349 (base ten) is divided by 2016 (base ten).

We want the minimum positive r such that

742770349 = p*2016 + r

start by factoring  the quotient

742770349 = p*2^5*3^2*7 + r

There are nice divisibility rules for 2^5 and 3^2 and in a pinch there are rules for 7
a number is divisible by 2^5=32 if its last 5 digits is divisible by 32
so we divide 70349 by 32 and find a remainder of 13.  Subtract this from both sides of the equation, then divide by 32

742770336 = p*2^5*3^2*7 + r - 13
23211573 = p*9*7 + (r-13)/32

a number is divisible by 9 if its digital sum is. 2+3+2+1+1+5+7+3 = 24 which is too big by 6.  So as before we will subtract from both sides and then divide.

23211567 = p*9*7 + (r-13)/32 -6
2579063 = p*7 + ((r-13)/32 -6)/9

Here's a method for finding the remainder for 7: http://www.cut-the-knot.org/blue/div7-11-13.shtml
it gives a remainder of 4, so one last subtract and divide

2579059 = p*7 + ((r-13)/32 -6)/9 - 4
368437 = p +  (((r-13)/32 -6)/9-4)/7

So 368437 is p, but only if the expression (((r-13)/32 -6)/9-4)/7 is zero, so solve
(((r-13)/32 -6)/9-4)/7 = 0
((r-13)/32 -6)/9-4 = 0
((r-13)/32 -6)/9 =4
(r-13)/32 -6 = 36
(r-13)/32 = 42
r - 13 = 1344
r = 1357

And as a check
2016 * 368437 + 1357 = 742770349

Posted by Jer on 2012-07-13 11:25:46