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.)
 re: Avoiding 98 mods (solution) | Comment 5 of 9 |
(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

Please log in:
 Login: Password: Remember me: Sign up! | Forgot password

 Search: Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information