Converse of Wilson's Theorem Proof, Beginner's Number Theory

In summary, this proof shows that if m is a composite number greater than 4, then (m-1)! is congruent to 0 (mod m). It also proves that if n divides (m-1)! + 1, it is impossible for p, a prime factor of m, to also divide (m-1)! + 1. The only exception to this proof is when m = 4, where (m-1)! is congruent to 2 (mod 4).
  • #1
cwatki14
57
0
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?
 
Physics news on Phys.org
  • #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.
 

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

What is Wilson's Theorem?

Wilson's Theorem is a mathematical theorem in number theory that states that a number n is prime if and only if (n-1)! + 1 is divisible by n.

What is the converse of Wilson's Theorem?

The converse of Wilson's Theorem states that if (n-1)! + 1 is divisible by n, then n is prime.

How do you prove the converse of Wilson's Theorem?

The converse of Wilson's Theorem can be proved using a proof by contradiction, assuming that n is composite and showing that this leads to a contradiction.

What is the importance of the converse of Wilson's Theorem?

The converse of Wilson's Theorem is important because it provides a way to generate prime numbers by checking if a number satisfies the condition (n-1)! + 1 is divisible by n. It also helps in proving the primality of large numbers.

Are there any exceptions to the converse of Wilson's Theorem?

Yes, there are a few exceptions to the converse of Wilson's Theorem, such as the numbers 4, 6, 8, and 12. These numbers satisfy the condition (n-1)! + 1 is divisible by n, but they are not prime.

Back
Top