Number Theory: show that (p-1)! = -1(mod p)

R

restin84

New member
Joined
Oct 24, 2011
Messages
7
I have an exercise to do for a course in Cryptography. We have an exercise with a couple proofs and I am having trouble finding a place to start on some of them.

Consider the group Z sub p with multiplication that has elements {1,2,....,p-1}

Consider (p-1)!. Recall that each element has a unique inverse. Show that (p-1)! = -1(mod p)

I am not looking for an answer as much as I am looking to be pointed in the right direction.
 
p! mod p is 0 so I know that p|p! ... I can also see (from some experimenting) that (p-1)! mod p = p-1
 
Experimenting or proving? How did you demonstrate it?
 
It actually does not work because 4! mod 5 = 4, 6! mod 7 = 6, but 8! mod 9 = 0.

I can show the p! mod p = 0 because p! = p(p-1)(p-2)...(2)(1) since p is a factor or p! then it must be true that p|p!

I am having a hard time working with (p-1)! I suppose. I know (p-1)! = (p-1)((p-1) -1)((p-1)-2)...(2)(1) = (p-1)(p-2)(p-3)...(2)(1) I am just not sure what I can say about it. How do I use it in such a way that it is relevant to the problem?
 
Last edited:
How's your Mathematical Induction.

1! = 1 = -1 mod 2
2! = 2 = -1 mod 3
3! = 6 = 2 mod 4 -- Whoops.
4! = 24 = -1 mod 5

I'm beginning to wonder if we have the right problem statement of if I actually understand what the problem statement is asking.
 
The problem statement is correct(partially) but the more I hear, the more I feel like I am getting a better understanding of what is happening. I realized that p should be prime. He does not state it in the exercises and assumes that we should know that it is a prime because he uses the letter p. It is my fault for making the same assumption that he made. Is that where the "oops" in your last post came from since 3! = 6 = 2 mod 4? Would this also mean that induction is not the way to go since I am not proving it for all positive integers?
 
Last edited:
From an algebraic standpoint, Zp is a field. The equation x^2=1 (mod p) has two solutions, x=1, and x=-1=p-1, and these are the only solutions. For every other element x^2=/=1. So every other element has a different and unique inverse. So...?
 
"Prime" was the missing piece, since there cannot be a factor of p in 2, 3, ..., (p-1). This was the problem when I tried p = 4.
 
You must log in or register to reply here.
Top