Wilson's Theorem gives a powerful connection between factorials and prime numbers. This cheat sheet helps students recognize when a number is prime using modular arithmetic and understand why factorial congruences matter in number theory. It is especially useful for contest math, proofs, and advanced algebra topics.
The reference focuses on formulas, conditions, and careful reasoning rather than long computations.
The central result is that an integer is prime exactly when . Students also need modular inverses, congruence notation, and efficient ways to detect composites before applying a factorial test. Wilson's Theorem is elegant but not always computationally efficient for large numbers.
The most important skill is knowing when the theorem proves primality and when simpler divisibility tests should be used first.
Key Facts
- Wilson's Theorem states that an integer is prime if and only if .
- The congruence is equivalent to .
- If and , then is composite.
- To test whether is prime by trial division, check divisibility only by primes with .
- For a prime , every nonzero residue modulo has a modular inverse such that .
- In the proof of Wilson's Theorem, most residues modulo a prime pair with their inverses, leaving only and because has solutions .
- For a prime , Wilson's Theorem can be rearranged as because .
- Wilson's Theorem is a true primality criterion, but computing is usually inefficient for large .
Vocabulary
- Prime number
- A prime number is an integer greater than whose only positive divisors are and itself.
- Composite number
- A composite number is an integer greater than that has at least one positive divisor other than and itself.
- Congruence
- The statement means that divides .
- Factorial
- The factorial is the product for positive integers .
- Modular inverse
- A modular inverse of modulo is a number such that .
- Primality test
- A primality test is a method used to decide whether a given integer is prime or composite.
Common Mistakes to Avoid
- Using Wilson's Theorem on is wrong because the theorem requires an integer and primality is only defined for integers greater than .
- Forgetting the negative residue is wrong because means the same as , not .
- Assuming Wilson's Theorem is fast for large numbers is wrong because calculating can require many multiplications.
- Checking divisibility past is unnecessary because if and both and , then .
- Claiming that only suggests primality is wrong because Wilson's Theorem gives an if and only if condition for .
Practice Questions
- 1 Use Wilson's Theorem to verify that is prime by computing .
- 2 Determine whether passes Wilson's Theorem by computing .
- 3 For the prime , find the value of without multiplying all factors.
- 4 Explain why Wilson's Theorem is useful for proving facts about primes but is usually not the best practical method for testing very large numbers.
Understanding Wilson's Theorem & Primality Reference
The proof idea depends on pairing each nonzero remainder with the number that multiplies by it to leave remainder one. For a prime modulus, every remainder from one up to one less than the prime has exactly one such partner. Most pairs have two different members, so each pair contributes remainder one to the full product.
Only two numbers pair with themselves. They are one and negative one, meaning the remainder one less than the prime. This happens because a number whose square leaves remainder one must satisfy a product of two factors that leaves remainder zero.
A prime cannot divide that product unless it divides one of the factors. That fact is called having no zero divisors.
Composite moduli behave differently because some nonzero remainders can multiply to give remainder zero. Their factors can appear inside the factorial product. For example, with twelve, the factors three and four are both present before twelve, and their product is divisible by twelve.
This helps explain why the factorial condition fails for composite inputs. The details need care for squares and small cases. With nine, the factor three occurs only once as a separate factor pair, but three times six is divisible by nine and both numbers occur in the factorial.
Four is a special small composite case where the factorial leaves remainder two rather than zero. The important point is that every composite number fails the test, though the reason for failure may not look identical in every case.
When working by hand, reduce after each multiplication instead of calculating a huge factorial first. To find the product before a prime p, multiply the current remainder by the next factor, then replace the result with its remainder on division by p. This keeps numbers manageable and makes errors easier to spot.
Modular inverses can often be found by inspection for small values. For instance, eleven is an inverse of seven modulo nineteen because seven times eleven leaves remainder one after division by nineteen.
For larger values, the Euclidean algorithm gives a systematic method. Students should remember that division in modular arithmetic really means multiplication by an inverse, and an inverse may not exist when the modulus is composite.
These ideas appear beyond classroom proofs. Many cryptography systems use arithmetic modulo primes because nonzero values have inverses, making calculations predictable and reversible. Wilson's result itself is rarely used to generate large primes because factorials grow far too quickly.
Faster primality methods are used in computing. In school problems, the theorem is more valuable as a lesson in precise logic.
A statement with if and only if works in both directions, so one successful factorial remainder proves primality while any different remainder proves compositeness. Check that the input is greater than one, distinguish congruence from ordinary equality, and use trial division first when a small factor may settle the problem quickly.