Wilson's Theorem remainder

  • Thread starter duki
  • Start date
  • #1
duki
264
0

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.
 

Answers and Replies

  • #2
matticus
107
1
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.
 
  • #3
duki
264
0
So do you do..

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

R = -18 + 37 = 19 ??
 
  • #4
Dick
Science Advisor
Homework Helper
26,263
621
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.
 
  • #5
duki
264
0
You're right. Thanks for the help.
 
  • #6
duki
264
0
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.
 
  • #7
Dick
Science Advisor
Homework Helper
26,263
621

Suggested for: Wilson's Theorem remainder

  • Last Post
Replies
12
Views
725
Replies
27
Views
2K
Replies
8
Views
309
  • Last Post
Replies
7
Views
332
Replies
2
Views
799
Replies
1
Views
238
Replies
1
Views
897
  • Last Post
Replies
5
Views
397
Replies
6
Views
392
Top