Congruences · Definition
Wilson's theorem
Before you start you need to know
This theorem links factorials with modular congruence and gives a classical characterization of prime numbers.
Definition
For a prime number \(p\), \((p-1)!\) leaves remainder \(-1\) when divided by \(p\).
If \(p\) is prime, every integer from \(1\) to \(p-1\) has an inverse modulo \(p\). The only elements that are their own inverses are \(1\) and \(-1\), so the others cancel in pairs in the product and the result is \(-1\).
Worked example: for \(p = 5\), the nonzero residues are \(1\), \(2\), \(3\) and \(4\), and \(1\cdot 2\cdot 3\cdot 4 = 24\), which leaves remainder \(4\), that is \(-1\) modulo \(5\). This checks the statement in a concrete case.
Common mistake: assuming the congruence holds for every integer \(n\). If \(n\) is composite it fails; for example, \(3! = 6\) leaves remainder \(2\) modulo \(4\), not \(-1\).
Think about it
Which elements of \(\{1,\dots,p-1\}\) are their own inverses modulo \(p\)?
Only \(1\) and \(-1\), because \(x^2 \equiv 1 \pmod{p}\) implies \(p \mid (x-1)(x+1)\).
Exercises 10
- What does Wilson's theorem state?
- What is the remainder of \(4!\) when divided by \(5\)?
- In Wilson's theorem, what condition must \(p\) satisfy?
- For \(p = 3\), what is \(2!\) modulo \(3\)?
- What does \((p-1)! \equiv -1 \pmod{p}\) mean?
- If \(n>1\) satisfies \((n-1)!\equiv -1 \pmod{n}\), what can you conclude about \(n\)?
- Modulo \(7\), which elements of \(\{1,2,\dots,6\}\) are their own inverses?
- What is \((p-1)! + 1\) modulo \(p\) for \(p = 5\)?
- Knowing that \(12! \equiv -1 \pmod{13}\), find the remainder of \(11!\) when divided by \(13\).
- For \(n = 4\), does \((n-1)! \equiv -1 \pmod{n}\) hold? Compute \(3!\) modulo \(4\) and compare with \(-1\) modulo \(4\).
References
- David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 5
- Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2