Question

Number theory...[yet again]

"Use Wilson's theorem to show that

\[(p-3)! \cong (p-1)\div2 \pmod{p}\]

for all prime numbers \[p \ge5\]

Answer 1

Well, wilson's theorem says that \((p-1)!\equiv -1\pmod{p}\). We also know that \((p-1)!=(p-3)!(p-2)(p-1)\). So if we multiply by \((p-1)^{-1}\) and \((p-2)^{-1}\), we should get what we want.

Answer 2

Since \(p-1\equiv -1\pmod{p}\), we know that \((p-1)^{-1}\equiv -1\pmod{p}\) as well, so we just multiply by p-1. Now we need to look at \(p-2\).

Is this making sense so far?

Answer 3

okay, no problem
I don't understand how you know that
'p-1≡ -1 (mod p) ?

Answer 4

I understand that (p-1)! ≡ -1 (mod p), but I don't understand why without the factorial, it is still ≡-1 ?

Answer 5

Well, \(p-1= qp+r\) for some \(q,r\), and by definition of mod, \(p-1\equiv r\pmod{p}\). Now we can take \(q=1\) and \(r=-1\), and we get that \(p-1\equiv -1\pmod{p}\)

Answer 6

right okay, yes I'm with you

Answer 7

And since \(-1*-1=1\), we know that \((p-1)^{-1}\equiv p-1\pmod{p}\).

Answer 8

Next, we want to find \((p-2)^{-1}\pmod{p}\). This is a little trickier. First, note that \((p-2)\equiv -2\pmod{p}\). So really, we're looking for \((-2)^{-1}\pmod{p}\).

Answer 9

Then, instead of actually computing it, we just write\[(-2)^{-1}:=-\frac{1}{2}.\]Finally, we multiply \(-1(p-1)(-1/2)=\frac{p-1}{2}\). (-1 comes from wilson's theorem, p-1 is inverse of p-1. and -1/2 is inverse of p-2).

Answer 10

And this is all done mod p of course.

Answer 11

oh I see!!

Answer 12

I should add the caveat that in general writing \(-1/2\) as \((-2)^{-1}\) is usually not the best way to write it. But in this case it's fine, since \(p-1\) is even for \(p\ge3\), and we're assuming \(p\ge 5\).

P.S. do you know what goes wrong if we don't assume \(p\ge5\)?

Answer 13

is it because with any \[p <5\] you with either end up with, 0! or something not defined...if not then no I don't know why :)

Answer 14

That's exactly it. If p=2 or 3, then \((p-3)!\) is either \((-1)!\) or \(0!\). Neither of which are equivalent to \((p-1)/2 \pmod{p}\).

Answer 15

right okay great! I follow that! Thanks so much! :)

Answer 16

You're welcome.