Remainder of 34! divided by 37 using Wilson's Theorem

[duki]

Homework Statement

Find the remainder when 34! is divided by 37.

Homework Equations

Wilson's Theorem

The Attempt at a Solution

I understand that (p-1)! = (-1)(mod p) and that (p-2)! = (1)(mod p). I don't understand how to apply this to (p-3)! though.

 

[matticus]

you know that (p-2)! = 1 (mod p). So (p-3)!*(p-2) = 1 (mod p). In this situation, 34!*35 = 1 (mod 37). Call 34! 'x' and then solve 35x = 1 mod 37, which has a unique solution since gcd(35,37) = 1.

 

[duki]

So do you do..

1 = 35x
1 = (-2)x
1 = (-2)(-18)

R = -18 + 37 = 19 ??

 

[Dick]

35*19 isn't 1 mod 37. Don't you mean 1=(-2)(-19)? It's easy enough to check your answers with a quick calculation.

 

[duki]

You're right. Thanks for the help.

 

[duki]

I'm trying to find 33! / 37 now.

I have gotten to (-3)x = 18 (mod 37)... but I can't figure out what x is.

 

[Dick]

http://en.wikipedia.org/wiki/Modular_multiplicative_inverse You use the extended euclidean algorithm to solve problems like that. Are you sure of your numbers this time?