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