Printable View
What is the remainder when 40! is divided by 1763?
I know this would be much easier if 1763 was prime, but it's not. So I don't see how Fermat's Little Theorem or Wilson's Theorem are applicable.
I know it comes down to 40! = x (mod 1763), but I don't see how I can manipulate this to find it easily. I thought of making it 37! * 38 * 39 * 40 = x (mod 1763) because 37 is prime, but I don't know if this helps.
Here's one way.Quote:
Originally Posted by Janu42
Prime factorization of 1763 is 41 * 43.
From Wilson's theorem, 40! is congruent to -1 (mod 41).
We know 42! is congruent to -1 (mod 43). So 42*41*40! is congruent to -1 (mod 43) which is congruent to 42 (mod 43). You can multiply each side by 42^(-1) and get 41*40! is congruent to 1 (mod 43). Then multiply each side by 41^(-1) which you can compute.
Then you can combine with CRT.
OK, so 40! = 41^(-1) (mod 43). But does that just mean it's 40! = 41 (mod 43)? Or is it something different?
The multiplicative inverse of 41 mod 43 turns out to be 21.Quote:
Originally Posted by Janu42
There is some discussion of modular inverses here.
http://www.mathhelpforum.com/math-he...ic-148985.html
Quote:
Originally Posted by undefined
OK thanks, I was thinking that it was the inverse before but I wasn't sure if I just messed up the sign in my calculations or something and it should have ended up as 41.