 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Factorial Remainder (Posted on 2011-09-02) Determine the remainder when 98! is divided by 101

*** For an extra challenge, solve this problem without using a computer program.

 See The Solution Submitted by K Sengupta Rating: 5.0000 (1 votes) Comments: ( Back to comment list | You must be logged in to post comments.) Solution | Comment 1 of 9

You would think this problem is very difficult because on the surface, it appears to deal with large numbers.  This usually causes most people to turn their brains off and reach for a calculator.

However, it is really only dealing with remainders, and remainders of 101 no less, so the maximum number of digits in each step is 3 (4 through n=99, if you count the multiplication as a separate step).

So for any n! mod 101 where n>1, all you do is repeat this process (For n=1, the answer is 1, and for those unfamiliar with the term mod, it is short for modulus, which means take the remainder after dividing.):

i=2
result=1
while i<=n
result=result*i mod 101

So, we get:

1*2=2 mod 101=2
2*3=6 mod 101=6
6*4=24 mod 101=24
24*5=120 mod 101=19
19*6=114 mod 101=13
13*7=91 mod 101=91
91*8=728 mod 101=21
21*9=189 mod 101=88
88*10=880 mod 101=72
.
.
.
82*90=7380 mod 101=7
7*91=637 mod 101=31
31*92=2852 mod 101=24
24*93=2232 mod 101=10
10*94=940 mod 101=31
31*95=2945 mod 101=16
16*96=1536 mod 101=21
21*97=2037 mod 101=17
17*98=1666 mod 101=50

So, 98! Mod 101=50.

 Posted by Joshua on 2011-09-02 14:39:46 Please log in:

 Search: Search body:
Forums (0)