Fermat's Theorem: Formula, Rules, Examples and Applications

Fermat's Theorem gives a method for simplifying powers in modular arithmetic when the modulus is prime. For a prime number p and an integer a not divisible by p, a^(p−1) leaves remainder 1 when divided by p. This page covers the theorem formula, exponent reduction, modular inverses, special cases and solved numerical examples.

On this page

What is Fermat's Theorem?

Fermat's Little Theorem states that if p is prime and p does not divide a, then a^(p−1) ≡ 1 (mod p). Equivalently, a^p ≡ a (mod p) for every integer a.

The notation a ≡ b (mod p) means that a and b have the same remainder on division by p. In the first form, the condition gcd(a,p)=1 is required. For example, since 5 is prime and 3 is not divisible by 5, 3^4 ≡ 1 (mod 5). Therefore, 3^8 ≡ 1 (mod 5).

Fermat's Theorem Formula & Tricks

Important Formulas

Fermat's standard form
If p is prime and p ∤ a, then a^(p−1) ≡ 1 (mod p).

Here, p ∤ a means that p does not divide a. The exponent can be reduced in multiples of p−1 when the base is relatively prime to p.

Fermat's universal form
a^p ≡ a (mod p), where p is prime and a is any integer.

This form also works when p divides a. It follows from the standard form when p does not divide a, and is immediate when p divides a.

Modular inverse using Fermat's theorem
If p is prime and p ∤ a, then a^−1 ≡ a^(p−2) (mod p).

The value a^(p−2) is the multiplicative inverse of a modulo p because a × a^(p−2) = a^(p−1) ≡ 1 (mod p).

Quick Tricks

Reduce the exponent modulo p−1

For a prime modulus p and a base not divisible by p, replace a large exponent n by its remainder when divided by p−1. If n = q(p−1)+r, then a^n ≡ a^r (mod p).

Example: To find 3^100 mod 7, reduce 100 modulo 6: 100 ≡ 4 (mod 6). Thus 3^100 ≡ 3^4 = 81 ≡ 4 (mod 7).
Check the base before using the shortcut

Exponent reduction modulo p−1 is not directly valid when p divides the base. In that case, use a^p ≡ a (mod p) or calculate the power using divisibility.

Example: For 10^100 mod 5, the base is divisible by 5, so 10^100 ≡ 0 (mod 5). Reducing 100 modulo 4 and treating the result as a standard Fermat case would be invalid.
Use the inverse formula for division modulo a prime

A division by a modulo p can be changed to multiplication by a^(p−2), provided p does not divide a.

Example: The inverse of 3 modulo 7 is 3^5 ≡ 5 (mod 7), since 3 × 5 = 15 ≡ 1 (mod 7).

Fermat's Theorem Concepts

Exponent reduction under a prime modulus

If p is prime and p does not divide a, powers of a repeat with period dividing p−1 modulo p.

For n = q(p−1)+r, Fermat's theorem gives a^n = a^[q(p−1)+r] ≡ (a^(p−1))^q × a^r ≡ a^r (mod p). The remainder r may be zero; in that case a^n ≡ 1 (mod p).

Example: For 7^222 mod 13, 222 = 18 × 12 + 6. Hence 7^222 ≡ 7^6 (mod 13). Since 7^2 ≡ 10, 7^6 ≡ 10^3 ≡ 12 (mod 13).

The two equivalent forms of the theorem

The forms a^(p−1) ≡ 1 (mod p), for p ∤ a, and a^p ≡ a (mod p), for every integer a, express the same prime-modulus property.

If p does not divide a, multiplying a^(p−1) ≡ 1 by a gives a^p ≡ a. If p divides a, both sides of a^p ≡ a are congruent to 0 modulo p.

Example: For p = 5 and a = 6, 6^5 ≡ 6 (mod 5), because both sides have remainder 1. The standard form can also be used: 6^4 ≡ 1 (mod 5).

Finding a modular inverse

For a prime p and p ∤ a, the inverse of a modulo p is a^(p−2) modulo p.

An inverse x satisfies ax ≡ 1 (mod p). Since a^(p−1) ≡ 1 (mod p), taking x = a^(p−2) gives ax = a^(p−1) ≡ 1 (mod p).

Example: The inverse of 4 modulo 11 is 4^9 mod 11. Since 4^5 ≡ 1 and 4^9 = 4^5 × 4^4 ≡ 1 × 3 ≡ 3 (mod 11), the inverse is 3; indeed, 4 × 3 = 12 ≡ 1 (mod 11).

Conditions and limitations

Fermat's standard formula requires a prime modulus and a base relatively prime to that modulus.

The rule a^(p−1) ≡ 1 (mod p) should not be applied when the modulus is composite or when p divides a. For a composite modulus, Euler's theorem or direct modular calculation may be appropriate, but the exponent period is not generally n−1.

Example: The modulus 8 is composite, and 3^7 = 2187 ≡ 3 (mod 8), not 1. Therefore, the prime-modulus form cannot be used with 8 as if it were prime.

Fermat's Theorem Video Lessons

Watch short topic-wise lessons for quick revision.

14 Lessons
Lesson 1 of 14 Quick Revision

Remainder Tricks: Fermat and Euler

Learn how Fermat’s pattern and Euler’s approach simplify remainder calculations for powers, including the key conditions and steps needed to apply these methods accurately.

Continue with more lessons and practice in PrepShots.Watch More in App - Start ₹1 Trial →
More Fermat's Theorem Lessons Scroll to explore →

Practice Fermat's Theorem Questions

Practise published questions related to this topic.

1Three bells ring together at 3:00 PM. They ring at intervals of 18 minutes, 24 minutes, and 32 minutes. After how much time will they ring together again?→ 2Find the greatest possible length which can be used to measure exactly the lengths 42 m, 63 m and 140 m.→ 3If √306.25 = 17.5, then what is the value of √0.00000030625?→ 4What is the smallest number which when increased by 17 is exactly divisible by 5, 6 and 8?→ 5Find the square root of 64009.→ 6What is the largest 2 digit number which is exactly divisible by both 9 and 3?→ 7If X = √289 × √225 × √144, then what is the value of x?→ 8If the ratio of two numbers is 2 : 5, and their HCF is 29, then their LCM is:→ 9The ratio of two numbers is 2 : 3 and their Least Common Multiple is 60. What are the two numbers?→ 10Find the lowest value for * in the number 3*760 such that the resulting number is divisible by 12.→

Fermat's Theorem Quick Quiz

Attempt 5 questions and check your score instantly.

Quick Revision Notes

Fermat's Theorem: Quick Revision

Use these conditions and formulas when simplifying powers modulo a prime.

  • For prime p and p ∤ a: a^(p−1) ≡ 1 (mod p).
  • For every integer a and prime p: a^p ≡ a (mod p).
  • When p ∤ a, reduce a large exponent modulo p−1.
  • If p divides the base, do not apply the standard exponent-reduction form directly.
  • For p ∤ a, the modular inverse is a^−1 ≡ a^(p−2) (mod p).
  • The standard Fermat formula requires a prime modulus; it is not a general rule for composite moduli.

Fermat's Theorem FAQs

What is the formula for Fermat's Theorem?

If p is prime and p does not divide a, then a^(p−1) ≡ 1 (mod p). Its universal form is a^p ≡ a (mod p) for every integer a.

How do you calculate 2^100 modulo 7 using Fermat's Theorem?

Since 7 is prime, reduce 100 modulo 6: 100 ≡ 4 (mod 6). Therefore, 2^100 ≡ 2^4 = 16 ≡ 2 (mod 7).

Can the exponent be reduced modulo p−1 when the base is divisible by p?

No. The reduction modulo p−1 requires p ∤ a. For example, 5^100 modulo 5 is 0, while reducing the exponent using the standard form would not be valid.

What is the modular inverse of 2 modulo 13 using Fermat's theorem?

The inverse is 2^(13−2) = 2^11 modulo 13. Since 2^12 ≡ 1 (mod 13), 2^11 ≡ 7 (mod 13), and 2 × 7 = 14 ≡ 1 (mod 13).

Does Fermat's Theorem apply when the modulus is composite?

The standard form a^(n−1) ≡ 1 (mod n) is not generally valid for composite n. For example, 3^7 ≡ 3 (mod 8), not 1; the modulus 8 is composite.

Continue learning Fermat's Theorem on PrepShots

Continue on PrepShots