Applying Fermat and Wilson's Theorem

Printable View

February 21st 2010, 08:43 AM
KatyCar

Applying Fermat and Wilson's Theorem

Hi everyone! I just had a couple questions about a few things I read in a textbook.

There were a couple points made that did not show any proof. I was able to prove some of them but the two listed below gave me some trouble. I like to see why things are so and need the proof in order to accept its validity. I was wondering if anyone here could help me prove these?

--- If b > 1 is not prime, then (b-1)! is not congruent to -1 (mod b)
--- If p is an odd prime, then (p-3)! ≡ (p-1)/2 (mod p)

Thank You!
February 21st 2010, 10:08 AM
o_O

#1: If you know Wilson's theorem, then what is the contrapositive of its statement?

#2: By Wilson's theorem, $(p-1)! \equiv - 1 \ (\text{mod } p)$

But: $(p-1)! = (p-1)(p-2)(p-3)!$

Can you finish off?
February 21st 2010, 04:52 PM
Bruno J.

Quote:

Originally Posted by o_O

#1: If you know Wilson's theorem, then what is the contrapositive of its statement?

#1 is not the contrapositive of Wilson's theorem!

Suppose $p|b$ , $p \neq b$ . Then $p|(b-1)!$ . If $(b-1)!+1\equiv 0 \mod b$ then $(b-1)!+1 = kb$ for some $k \in \mathbb{Z}$ . Now $p|b, p|(b-1)!$ but $p \nmid 1$ , which is impossible.
February 21st 2010, 05:03 PM
o_O

Hmm .. you sure? Wilson's theorem is a biconditional statement. So if we take the direction that: $(b-1)! \equiv -1 \ (\text{mod b}) \ \Rightarrow \ b \text{ is prime.}$

Then this is logically equivalent to saying if b is not prime, then etc. etc.
February 21st 2010, 06:06 PM
Bruno J.

Oh, in that case you are correct! In my mind Wilson's theorem was "If $p$ is prime, then $(p-1)! \equiv -1 \mod p$ ", but it makes sense to include the other direction as well.