Without actual evaluation, determine the
last 3 nonzero digits of:
33! - 23!
As observed by Larry, we only need to compute the last three digits preceding the terminal zeros of 23! and subtract that from 1000 to get our answer.
Equivalently I could say we want to calculate -1 * 23! / (10^4) mod 1000.
Lets start by expanding 23!, but I'm going to group the terms in a special order:
(-1*12*17) * (2*5*10*15*20) * (7*11*31) * (8*9*14) * (3*16*21) * (4*22*23) * (6*18*19) / 10^4
Now each group gets some evaluation:
-1*12*17 stays as is for now.
2*5*10*15*20 cancels out the 10^4 leaving behind 3.
7*11*31 = 1001 = 1 mod 1000
8*9*14 = 1008 = 8 mod 1000
3*16*21 = 1008 = 8 mod 1000
4*22*23 = 2*1012 = 2*12 mod 1000
6*18*19 = 2*1026 = 2*26 mod 1000
Now we can plug all this in and get:
-1*12*17 * 3 * 1 * 8 * 8 * 2*12 * 2*26 mod 1000
A bit of rearrangement gives (-1*2^2*13) * (2*3^3*17) * (2^10) mod 1000
-1*2^2*13 stays as is for now
2*3^3*17 = 918 = -82 mod 1000
2^10 = 1024 = 24 mod 1000
Now we are down to -1*2^2*13 * -82 * 24 mod 1000
One more grouping: (-1*-82*13) * (2^2*24)
-1*-82*13 = 1066 = 66 mod 1000
So now down to 66*4*24 mod 1000
11*4*24 = 1056 = 56 mod 1000, which leaves 6*56 = 336 as the answer. (And during this whole solution the largest number I had to ever compute was 1066.)
Pencil and Paper
