Fermat’s Little Theorem and Wilson’s Theorem Applications
Quantitative Aptitude › Number System · Topic 1.9
Fermat's Little Theorem says that if p is a prime and a is not divisible by p, then ap-1 leaves remainder 1 on division by p. Wilson's Theorem says that (p - 1)! leaves remainder p - 1 on division by a prime p.
5 min read · Quantitative Aptitude · Number System
Quick Answer
Fermat’s Little Theorem says that if p is a prime and a is not divisible by p, then ap-1 leaves remainder 1 on division by p. Wilson’s Theorem says that (p – 1)! leaves remainder p – 1 on division by a prime p.
At a Glance
- Fermat ap-1 ≡ 1 (mod p)
- Condition p prime and p does not divide a
- Wilson (p – 1)! ≡ -1 (mod p)
- Corollary (p – 2)! ≡ 1 (mod p)
- Use Reduce large powers and factorials
- Exponent step Reduce the power modulo p – 1
Where Does It Fit?
This topic follows Remainder Theorem and Chinese Remainder Theorem and uses the remainder rules explained there. It applies to powers and factorials, which connects to Factorial Values and Number of Trailing Zeros in a Factorial and Cyclicity of Numbers in Finding Unit Digits.
What Does Fermat’s Little Theorem Say?
In short: for a prime p and a number a not divisible by p, the power ap-1 leaves remainder 1 on division by p.
Fermat
- ap-1 ≡ 1 (mod p) when p is prime and p does not divide a.
- So the powers of a repeat with a cycle that divides p – 1.
| Prime p | a | ap-1 | Remainder |
|---|---|---|---|
| 7 | 3 | 36 = 729 | 1 |
| 11 | 2 | 210 = 1,024 | 1 |
| 13 | 2 | 212 = 4,096 | 1 |
| 5 | 4 | 44 = 256 | 1 |
If p divides a, then ap-1 leaves remainder 0, so the theorem does not apply. Large powers are reduced by taking the exponent modulo p – 1. For 3100 divided by 7: 100 = 6 × 16 + 4, so the remainder is that of 34 = 81, which is 4.
What Does Wilson’s Theorem Say?
In short: for a prime p, the factorial (p – 1)! leaves remainder p – 1, which is the same as -1.
Wilson
- (p – 1)! ≡ -1 (mod p), that is, remainder p – 1, for a prime p.
- Corollary: (p – 2)! ≡ 1 (mod p).
| p | (p – 1)! | Remainder |
|---|---|---|
| 5 | 4! = 24 | 4 |
| 7 | 6! = 720 | 6 |
| 11 | 10! = 36,28,800 | 10 |
| 13 | 12! = 47,90,01,600 | 12 |
Wilson’s theorem is also a test for primes, because (n – 1)! leaves remainder n – 1 only when n is prime, but it is not used for large numbers. The corollary gives 5! = 120, which leaves remainder 1 on division by 7.
How Do You Use These Theorems in Problems?
In short: check that the divisor is prime, reduce the exponent or the factorial, and finish with ordinary remainder rules from Remainder Theorem and Chinese Remainder Theorem.
- For a power: reduce the exponent modulo p – 1. For 22025 divided by 13: 2025 = 12 × 168 + 9, so the remainder is that of 29 = 512, which is 5.
- For a factorial just below a multiple: use Wilson. 10! on division by 11 leaves 10.
- If the divisor is not prime, use a cycle or the Chinese Remainder Theorem instead.
Solved Examples
Example 1
Question: Find the remainder when 3100 is divided by 7.
- 7 is prime and does not divide 3, so 36 leaves remainder 1.
- 100 = 6 × 16 + 4.
- The remainder equals that of 34 = 81, and 81 = 7 × 11 + 4.
Answer: 4.
Example 2
Question: Find the remainder when 250 is divided by 11.
- 210 leaves remainder 1 by Fermat’s theorem.
- 50 = 10 × 5.
- So 250 = (210)5 leaves remainder 1.
Answer: 1.
Example 3
Question: Find the remainder when 22025 is divided by 13.
- 212 leaves remainder 1.
- 2025 = 12 × 168 + 9.
- 29 = 512 = 13 × 39 + 5.
Answer: 5.
Example 4
Question: Find the remainder when 10! is divided by 11.
- 11 is prime, so by Wilson’s theorem (11 – 1)! ≡ -1 (mod 11).
- -1 corresponds to the remainder 11 – 1 = 10.
Answer: 10.
Example 5
Question: Find the remainder when 5! is divided by 7.
- By Wilson, 6! ≡ -1 (mod 7).
- 6! = 6 × 5!, and 6 ≡ -1, so -5! ≡ -1, giving 5! ≡ 1.
- Check: 5! = 120 = 7 × 17 + 1.
Answer: 1.
Shortcuts and Tricks
- Always check that the divisor is prime and does not divide the base.
- Reduce the exponent modulo p – 1 before computing.
- Use (p – 1)! ≡ -1 and (p – 2)! ≡ 1 for factorial questions.
- If the divisor is composite, split it into co-prime factors.
- Use small cycles when they exist; 2 has cycle 10 for 11.
Common Mistakes
- Using Fermat’s theorem when the divisor is not prime.
- Using it when the base is a multiple of p.
- Reducing the exponent modulo p instead of modulo p – 1.
- Writing the final remainder as -1 instead of p – 1.
- Applying Wilson’s theorem to composite numbers.
Practice Questions
- What is the remainder when 6! is divided by 7?
- What is the remainder when 12! is divided by 13?
- What is the remainder when 3100 is divided by 7?
- What is the remainder when 250 is divided by 11?
- What is the remainder when 22025 is divided by 13?
- What is the remainder when 5! is divided by 7?
Answers: 1) 6; 2) 12; 3) 4; 4) 1; 5) 5; 6) 1.
Why Is This Topic Important?
- Shortcut Reduces huge powers and factorials to tiny calculations.
- CAT use Appears in number theory sets at CAT level.
- Link Builds on remainders in Remainder Theorem and Chinese Remainder Theorem.
- Link Extends cyclic ideas in Cyclicity of Numbers in Finding Unit Digits.
What Comes Next?
The next topic is Base Conversion (Binary, Octal, Hexadecimal to Decimal and Vice Versa), which changes numbers between binary, octal, hexadecimal and decimal.
Key Terms and Formulas
- Fermat’s Little Theorem ap-1 ≡ 1 (mod p)
- Wilson’s Theorem (p – 1)! ≡ -1 (mod p)
- Prime modulus A prime used as the divisor
- Congruence Equal remainders
- Corollary (p – 2)! ≡ 1 (mod p)
- Cycle length Exponent after which remainders repeat
Related Topics
- Remainder Theorem and Chinese Remainder Theorem
- Base Conversion (Binary, Octal, Hexadecimal to Decimal and Vice Versa)
- Classification of Numbers (Natural, Whole, Integers, Rational, Irrational and Real Numbers)
- Face Value and Place Value of Digits
Exam Corner
Points to Remember
- Fermat: ap-1 leaves remainder 1 when p is prime and does not divide a.
- Wilson: (p – 1)! leaves remainder p – 1.
- Reduce the exponent modulo p – 1.
- The theorems need a prime divisor.
- (p – 2)! leaves remainder 1.
Do Not Confuse With
- Fermat vs Wilson Fermat is about powers; Wilson is about factorials.
- p – 1 vs p The exponent reduces modulo p – 1, not modulo p.
- Remainder -1 vs p – 1 Both describe the same remainder class.
- Prime vs composite divisor The theorems hold only for primes.
Memory Hook
Fermat: power p minus one gives one; Wilson: factorial p minus one gives minus one.
GS Relevance
Frequently Asked Questions
What is Fermat's Little Theorem?
Fermat's Little Theorem states that if p is a prime number and a is not divisible by p, then a raised to the power p minus 1 leaves remainder 1 when divided by p. For example, 3 to the power 6 equals 729, which leaves remainder 1 on division by 7.
What is Wilson's Theorem?
Wilson's Theorem states that for a prime number p, the factorial of p minus 1 leaves remainder p minus 1 when divided by p, which is the same as negative 1. For example, 6 factorial is 720, which leaves remainder 6 when divided by 7.
How do you use Fermat's theorem for large powers?
Check that the divisor is prime and does not divide the base, then reduce the exponent modulo the divisor minus 1. For 3 to the power 100 divided by 7, the exponent 100 leaves 4 on division by 6, so the remainder is that of 3 to the power 4, which is 4.
What is the remainder when 10 factorial is divided by 11?
The remainder when 10 factorial is divided by 11 is 10. Wilson's Theorem states that for the prime 11, the factorial of 10 is congruent to negative 1 modulo 11, and negative 1 corresponds to the remainder 10. Direct calculation gives 36,28,800, which leaves remainder 10.
Can Fermat's theorem be used for composite divisors?
Fermat's theorem cannot be used directly for composite divisors, because it requires a prime modulus. For a composite divisor, split it into pairwise co-prime factors and apply the theorem to prime factors where possible, or use the cycle of remainders and the Chinese Remainder Theorem.
PYQ Practice — Statement Analysis
1 The remainder when 6! is divided by 7 is 6.
By Wilson's theorem, (7 - 1)! ≡ -1, which is 6.
2 Fermat's Little Theorem holds for every divisor.
It requires a prime divisor.
3 The remainder when 250 is divided by 11 is 1.
210 leaves 1, and 50 is a multiple of 10.
4 The remainder when 5! is divided by 7 is 1.
120 = 7 × 17 + 1.
Related Topics
Browse the full Quantitative Aptitude index