HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
The Theorems of Fermat, Euler and Wilson
  1. 1Fermat's little theorem
  2. 2Euler's totient function and theorem
  3. 3Wilson's theorem and the order of a number
  1. Mathematics
  2. /The Theorems of Fermat, Euler and Wilson
  3. /Wilson's theorem and the order of a number

Course 28.2·Lesson 3 of 3

Wilson's theorem and the order of a number

Wilson's theorem says that (p−1)!≡−1(modp)(p - 1)! \equiv -1 \pmod p(p−1)!≡−1(modp)

Lesson 3 of 3Show all lessonsHide
The Theorems of Fermat, Euler and Wilson
  1. 1Fermat's little theorem
  2. 2Euler's totient function and theorem
  3. 3Wilson's theorem and the order of a number

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 nnn, and use the fact that it divides φ(n)\varphi(n)φ(n);
  • explain the length of a repeating decimal and decide when x2≡−1(modp)x^2 \equiv -1 \pmod px2≡−1(modp) can be solved.

Pairs that cancel

Look at 1,2,…,101, 2, \dots, 101,2,…,10 modulo 111111. Pair each number with its inverse: 222 with 666, 333 with 444, 555 with 999, 777 with 888. Each pair multiplies to 111 modulo 111111. Only 111 and 101010 are left alone, because each is its own inverse. So

10!≡1×10×(1)(1)(1)(1)=10≡−1(mod11).\displaystyle 10! \equiv 1 \times 10 \times (1)(1)(1)(1) = 10 \equiv -1 \pmod{11}.10!≡1×10×(1)(1)(1)(1)=10≡−1(mod11).

Wilson's theorem

Wilson's theorem. For every prime ppp,

(p−1)!≡−1(modp).\displaystyle (p - 1)! \equiv -1 \pmod p.(p−1)!≡−1(modp).

Proof. For p=2p = 2p=2 and p=3p = 3p=3 check directly: 1!=1≡−1(mod2)1! = 1 \equiv -1 \pmod 21!=1≡−1(mod2) and 2!=2≡−1(mod3)2! = 2 \equiv -1 \pmod 32!=2≡−1(mod3). For p≥5p \ge 5p≥5, every number from 111 to p−1p - 1p−1 has an inverse modulo ppp. A number is its own inverse when a2≡1a^2 \equiv 1a2≡1, that is p∣(a−1)(a+1)p \mid (a - 1)(a + 1)p∣(a−1)(a+1), so a=1a = 1a=1 or a=p−1a = p - 1a=p−1. The other p−3p - 3p−3 numbers fall into pairs with product 111. So (p−1)!≡1⋅(p−1)≡−1(p - 1)! \equiv 1 \cdot (p - 1) \equiv -1(p−1)!≡1⋅(p−1)≡−1.

The converse. If n>4n > 4n>4 is composite, then (n−1)!≡0(modn)(n - 1)! \equiv 0 \pmod n(n−1)!≡0(modn). Write n=abn = abn=ab with 1<a≤b<n1 < a \le b < n1<a≤b<n. If a<ba < ba<b, both are factors of (n−1)!(n - 1)!(n−1)!. If a=ba = ba=b, then n=a2n = a^2n=a2 with a≥3a \ge 3a≥3, and aaa and 2a2a2a are both at most n−1n - 1n−1. For n=4n = 4n=4, 3!=6≡23! = 6 \equiv 23!=6≡2. So (n−1)!≡−1(modn)(n - 1)! \equiv -1 \pmod n(n−1)!≡−1(modn) holds exactly when nnn 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 ppp. Take p=31p = 31p=31 and find 28!28!28! modulo 313131.

  1. Wilson. 30!≡−130! \equiv -130!≡−1.
  2. Peel off two factors. 30!=30×29×28!≡(−1)(−2)⋅28!=2⋅28!30! = 30 \times 29 \times 28! \equiv (-1)(-2) \cdot 28! = 2 \cdot 28!30!=30×29×28!≡(−1)(−2)⋅28!=2⋅28!.
  3. Solve. 2⋅28!≡−1≡302 \cdot 28! \equiv -1 \equiv 302⋅28!≡−1≡30, so 28!≡15(mod31)28! \equiv 15 \pmod{31}28!≡15(mod31).

The order of a number

Let gcd⁡(a,n)=1\gcd(a, n) = 1gcd(a,n)=1. The order of aaa modulo nnn is the smallest positive kkk with ak≡1(modn)a^k \equiv 1 \pmod nak≡1(modn). We write ord⁡n(a)\operatorname{ord}_n(a)ordn​(a).

Modulo 131313 the order of 333 is 333, since 33=27≡13^3 = 27 \equiv 133=27≡1. The order of 222 is 121212: no smaller power of 222 gives 111.

Key fact. am≡1(modn)a^m \equiv 1 \pmod nam≡1(modn) exactly when ord⁡n(a)\operatorname{ord}_n(a)ordn​(a) divides mmm. Divide mmm by the order ddd: m=qd+rm = qd + rm=qd+r with 0≤r<d0 \le r < d0≤r<d. Then am≡ara^m \equiv a^ram≡ar, and ar≡1a^r \equiv 1ar≡1 forces r=0r = 0r=0, since ddd is the smallest.

So the order divides φ(n)\varphi(n)φ(n), and modulo a prime it divides p−1p - 1p−1. To find an order, test only the divisors of φ(n)\varphi(n)φ(n).

A number whose order is φ(n)\varphi(n)φ(n) is a primitive root. Modulo every prime there is one: 222 is a primitive root modulo 131313. This fact is proved in a first university course; olympiads use it as known.

Repeating decimals. The decimal of 1p\dfrac{1}{p}p1​ repeats with period ord⁡p(10)\operatorname{ord}_p(10)ordp​(10), for a prime ppp other than 222 and 555. For 17=0.142857‾\dfrac{1}{7} = 0.\overline{142857}71​=0.142857 the period is 666, and 101010 is a primitive root modulo 777. For 113\dfrac{1}{13}131​ the period is 666, a divisor of 121212.

When is −1-1−1 a square?

Can x2≡−1(modp)x^2 \equiv -1 \pmod px2≡−1(modp) be solved for an odd prime ppp?

  • If p≡1(mod4)p \equiv 1 \pmod 4p≡1(mod4): yes. Pair kkk with p−k≡−kp - k \equiv -kp−k≡−k in (p−1)!(p - 1)!(p−1)!. This gives (p−1)!≡(−1)(p−1)/2[(p−12)!]2(p - 1)! \equiv (-1)^{(p-1)/2} \left[\left(\tfrac{p-1}{2}\right)!\right]^2(p−1)!≡(−1)(p−1)/2[(2p−1​)!]2. The sign is +++ because p−12\tfrac{p-1}{2}2p−1​ is even, so Wilson gives [(p−12)!]2≡−1\left[\left(\tfrac{p-1}{2}\right)!\right]^2 \equiv -1[(2p−1​)!]2≡−1.
  • If p≡3(mod4)p \equiv 3 \pmod 4p≡3(mod4): no. If x2≡−1x^2 \equiv -1x2≡−1, then xp−1=(x2)(p−1)/2≡(−1)(p−1)/2=−1x^{p-1} = (x^2)^{(p-1)/2} \equiv (-1)^{(p-1)/2} = -1xp−1=(x2)(p−1)/2≡(−1)(p−1)/2=−1, against Fermat.

For p=13p = 13p=13: 6!=720=55×13+56! = 720 = 55 \times 13 + 56!=720=55×13+5, and 52=25≡−1(mod13)5^2 = 25 \equiv -1 \pmod{13}52=25≡−1(mod13).

Practise with new numbers

Try it in Python

The program prints (n−1)!(n - 1)!(n−1)! modulo nnn for nnn from 222 to 161616, then the orders of 111 to 121212 modulo 131313.

Read it first. Then run it. For which nnn is the remainder n−1n - 1n−1?

1. Which orders appear modulo 131313? Check that each one divides 121212.

2. Change order(10, 7) to order(10, 17). How long is the repeating block of 1/171/171/17?

Common mistakes

  • Applying Wilson to a composite. (n−1)!≡−1(n - 1)! \equiv -1(n−1)!≡−1 holds only for primes.
  • Forgetting the signs when peeling factors. p−1≡−1p - 1 \equiv -1p−1≡−1 and p−2≡−2p - 2 \equiv -2p−2≡−2.
  • Testing every kkk for an order. Only the divisors of φ(n)\varphi(n)φ(n) can be orders.
  • Thinking every number is a primitive root. Modulo 131313, the number 333 has order 333, not 121212.

Remember these

  • (p−1)!≡−1(modp)(p - 1)! \equiv -1 \pmod p(p−1)!≡−1(modp) exactly when ppp is prime.
  • ord⁡n(a)\operatorname{ord}_n(a)ordn​(a) divides every mmm with am≡1a^m \equiv 1am≡1, so it divides φ(n)\varphi(n)φ(n).
  • The period of 1/p1/p1/p is ord⁡p(10)\operatorname{ord}_p(10)ordp​(10).
  • x2≡−1(modp)x^2 \equiv -1 \pmod px2≡−1(modp) is solvable exactly when p=2p = 2p=2 or p≡1(mod4)p \equiv 1 \pmod 4p≡1(mod4).

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. Find the remainder of 16!16!16! on division by 171717.
  1. Find the remainder of 15!15!15! on division by 171717.
  1. Find the order of 222 modulo 111111.
  1. What is 5!5!5! modulo 666? Does this agree with the converse of Wilson?
  1. Can x2+1x^2 + 1x2+1 be a multiple of 191919?

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.
No payment. You can leave at any time.

Problems (3)

The numbers 43 and 97 are prime. Use Wilson's theorem to find the remainder of 40! …Hard · High School (11–12) · by StemPy Lab
The decimal of 1/41 repeats, and so does the decimal of 1/17…Advanced · High School (11–12) · by StemPy Lab
Prove that if p is a prime with p ≡ 1 pmod 4, then x = ((p - 1)/2)! …Advanced · High School (11–12) · by StemPy Lab
That was the last lessonBack to the course: take the test
← The Theorems of Fermat, Euler and Wilson
← Euler's totient function and theoremNext →

Discussion (0)

Log in to join the discussion.

Loading…

for every prime
ppp
, and the converse holds: for a composite
nnn
above
444
,
(n−1)!≡0(modn)(n - 1)! \equiv 0 \pmod n(n−1)!≡0(modn)
. The order of
aaa
modulo
nnn
is the smallest
kkk
with
ak≡1a^k \equiv 1ak≡1
; it divides
φ(n)\varphi(n)φ(n)
. Orders explain repeating decimals, and Wilson shows when
−1-1−1
is a square modulo a prime.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

Python Labs (1)

Orders, primitive roots and WilsonPython Lab · by StemPy Lab

Question Sets (1)

Fermat, Euler and Wilson: Think It Through10 questions · by StemPy Lab

Notes (1)

Fermat, Euler and Wilson: Quick RevisionNote · by StemPy Lab