Wilson's Theorem remainder

  • Thread starter duki
  • Start date
  • #1
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
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
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,260
619
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
264
0
You're right. Thanks for the help.
 
  • #6
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,260
619

Related Threads on Wilson's Theorem remainder

  • Last Post
Replies
4
Views
947
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
17
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
12
Views
2K
Top