1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Converse of Wilson's Theorem Proof, Beginner's Number Theory

  1. Feb 25, 2010 #1
    Prove this converse of Wilson’s Theorem: if m > 4 is a composite number then (m − 1)! ≡ 0 (mod m). (Note: This isn’t true for m = 4, so make sure that this fact is reflected in your proof.)
    My train of thought...:
    If m is composite, which has a prime factors r and s such that r does not equal s, then m divides (m-1)! then (m-1)! is congruent to 0 (mod m).

    Now consider the case of m=p^2 where p is a prime.
    If m> 2p then px2p divides (m-1)! therefore (m-1)! is congruent to 0 (mod m).
    If m<= 2p then 2p>= p^2 by dividing each side by p we show that 2 >=p. The only case that exists when p=2. We can note the 3! is congruent to 2 (mod4).

    Thus we have proven that (m-1)! is not congruent to -1 (mod m) is m is composite. In fact, when m is any composite besides 4, (m-1)! is congruent to 0 (mod m)

    Also, we can note if m is composite that it has prime factors such that p<m. Hence if n divides (m-1)!+1 then p also divides (m-1)! +1. This is impossible because p divides (m-1)! and it can not divide (m-1)!+1

    Does this suffice for the proof?
  2. jcsd
  3. Feb 26, 2010 #2
    In your second to last sentence, what is n? Apart from that, this almost suffices as a proof. The part that concerns me is that r and s being prime factors of m doesn't imply that m divides (m-1)!. Rather, you need two nontrivial factors that multiply to m. If you fix that part, you should be done. The only other thing you might want to clarify a little more in your writeup, even if it seems obvious to you, is that only numbers of the form p^2 do not have two different factors r and s such that rs = p^2.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook