Determine the remainder when 98! is divided by 101

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

(In reply to Avoiding 98 mods (solution) by Steve Herman)

I thought it had to do with Wilson's Theorem, but the math and symbology in the pages I found on it were over my head. :)

Maybe you could explain, what does it mean to say 1 (mod 101), and further to say 2*51=3*34...=1 (mod 101)?

Oh, I get it, they are all the mod operation is 1 if n is prime and the divisor.  So since 101 is prime, n-2=99, and so 99! mod 101=1.

So from there, you could find out what 100! mod 101 is brilliant.

Combining our posts, you get:

98! MOD 101
= (100!/(99*100)) MOD 101
= ((99!*100)/(99*100)) MOD 101

and used the distributive property of MOD:

=((99! MOD 101)*(100 MOD 101))/((99*100) MOD 101)) MOD 101

and reduced using Wilson's Theorem that ((n-2)! mod n) = 1 (providing n is prime):

=((1*100)/(9900 MOD 101)) MOD 101

reducing by performing the second mod:

=(100/2) MOD 101

dividing:

=50 MOD 101

and the final mod (for a count of three or four if you count 100 mod 101 :) )!

=50

Edited on September 3, 2011, 4:59 am

Posted by Joshua on 2011-09-02 22:19:17