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 + (r13)/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 + (r13)/32 6
2579063 = p*7 + ((r13)/32 6)/9
Here's a method for finding the remainder for 7: http://www.cuttheknot.org/blue/div71113.shtml
it gives a remainder of 4, so one last subtract and divide
2579059 = p*7 + ((r13)/32 6)/9  4
368437 = p + (((r13)/32 6)/94)/7
So
368437 is p, but only if the expression (((r13)/32 6)/94)/7 is zero, so solve
(((r13)/32 6)/94)/7 = 0
((r13)/32 6)/94 = 0
((r13)/32 6)/9 =4
(r13)/32 6 = 36
(r13)/32 = 42
r  13 = 1344
r = 1357And as a check
2016 * 368437 + 1357 = 742770349

Posted by Jer
on 20120713 11:25:46 