# Remainder Problem

• Sep 30th 2010, 10:05 AM
Janu42
Remainder Problem
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.
• Sep 30th 2010, 10:36 AM
undefined
Quote:

Originally Posted by Janu42
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.

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.
• Sep 30th 2010, 11:35 AM
Janu42
OK, so 40! = 41^(-1) (mod 43). But does that just mean it's 40! = 41 (mod 43)? Or is it something different?
• Sep 30th 2010, 12:11 PM
undefined
Quote:

Originally Posted by Janu42
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.

There is some discussion of modular inverses here.

http://www.mathhelpforum.com/math-he...ic-148985.html
• Sep 30th 2010, 01:39 PM
Janu42
Quote:

Originally Posted by undefined
The multiplicative inverse of 41 mod 43 turns out to be 21.

There is some discussion of modular inverses here.

http://www.mathhelpforum.com/math-he...ic-148985.html

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.