Try the code and the simulations beside the lesson.
What you will be able to do
state and prove Wilson's theorem, and use it to find factorials modulo a prime;
find the order of a number modulo n, and use the fact that it divides φ(n);
explain the length of a repeating decimal and decide when x2≡−1(modp) can be solved.
Pairs that cancel
Look at 1,2,…,10 modulo 11. Pair each number with its inverse: 2 with 6, 3 with 4, 5 with 9, 7 with 8. Each pair multiplies to 1 modulo 11. Only 1 and 10 are left alone, because each is its own inverse. So
10!≡1×10×(1)(1)(1)(1)=10≡−1(mod11).
Wilson's theorem
Wilson's theorem. For every prime p,
(p−1)!≡−1(modp).
Proof. For p=2 and p=3 check directly: 1!=1≡−1(mod2) and 2!=2≡−1(mod3). For p≥5, every number from 1 to p−1 has an inverse modulo p. A number is its own inverse when a2≡1, that is p∣(a−1)(a+1), so a=1 or a=p−1. The other p−3 numbers fall into pairs with product 1. So (p−1)!≡1⋅(p−1)≡−1.
The converse. If n>4 is composite, then (n−1)!≡0(modn). Write n=ab with 1<a≤b<n. If a<b, both are factors of (n−1)!. If a=b, then n=a2 with a≥3, and a and 2a are both at most n−1. For n=4, 3!=6≡2. So (n−1)!≡−1(modn) holds exactly when n is prime.
The numbers 1 to 10 placed round a circle, for the prime 11. Lines join the pairs whose product is 1 modulo 11: 2 with 6, 3 with 4, 5 with 9 and 7 with 8. The numbers 1 and 10 are circled in red: each is its own partner. A note says 10! is congruent to 1 times 10, which is -1, modulo 11.
Factorials near a prime
Wilson gives the remainders of factorials just below p. Take p=31 and find 28! modulo 31.
Wilson.30!≡−1.
Peel off two factors.30!=30×29×28!≡(−1)(−2)⋅28!=2⋅28!.
Solve.2⋅28!≡−1≡30, so 28!≡15(mod31).
The order of a number
Let gcd(a,n)=1. The order of a modulo n is the smallest positive k with ak≡1(modn). We write ordn(a).
Modulo 13 the order of 3 is 3, since 33=27≡1. The order of 2 is 12: no smaller power of 2 gives 1.
Key fact.am≡1(modn) exactly when ordn(a) divides m. Divide m by the order d: m=qd+r with 0≤r<d. Then am≡ar, and ar≡1 forces r=0, since d is the smallest.
So the order divides φ(n), and modulo a prime it divides p−1. To find an order, test only the divisors of φ(n).
A number whose order is φ(n) is a primitive root. Modulo every prime there is one: 2 is a primitive root modulo 13. This fact is proved in a first university course; olympiads use it as known.
Repeating decimals. The decimal of p1 repeats with period ordp(10), for a prime p other than 2 and 5. For 71=0.142857 the period is 6, and 10 is a primitive root modulo 7. For 131 the period is 6, a divisor of 12.
When is −1 a square?
Can x2≡−1(modp) be solved for an odd prime p?
If p≡1(mod4): yes. Pair k with p−k≡−k in (p−1)!. This gives (p−1)!≡(−1)(p−1)/2[(2p−1)!]2. The sign is + because 2p−1 is even, so Wilson gives [(2p−1)!]2≡−1.
If p≡3(mod4): no. If x2≡−1, then xp−1=(x2)(p−1)/2≡(−1)(p−1)/2=−1, against Fermat.
For p=13: 6!=720=55×13+5, and 52=25≡−1(mod13).
Practise with new numbers
Try it in Python
The program prints (n−1)! modulo n for n from 2 to 16, then the orders of 1 to 12 modulo 13.
Common mistakes
Applying Wilson to a composite.(n−1)!≡−1 holds only for primes.
Forgetting the signs when peeling factors.p−1≡−1 and p−2≡−2.
Testing every k for an order. Only the divisors of φ(n) can be orders.
Thinking every number is a primitive root. Modulo 13, the number 3 has order 3, not 12.
Remember these
(p−1)!≡−1(modp) exactly when p is prime.
ordn(a) divides every m with am≡1, so it divides φ(n).
The period of 1/p is ordp(10).
x2≡−1(modp) is solvable exactly when p=2 or p≡1(mod4).
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Find the remainder of 16! on division by 17.
Find the remainder of 15! on division by 17.
Find the order of 2 modulo 11.
What is 5! modulo 6? Does this agree with the converse of Wilson?
Can x2+1 be a multiple of 19?
References
David M. Burton, Elementary Number Theory, Chapter 5, section on Wilson's theorem, and Chapter 8, Primitive Roots and Indices.
Enroll free in The Theorems of Fermat, Euler and Wilson
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.