✦ScienexySCIENCE KNOWLEDGE LIBRARY
theorem · SCI-MAT-002-078

Fermat's Little Theorem

Fermat's Little Theorem states that if p is prime and p does not divide a, then a raised to the power p − 1 is congruent to 1 modulo p.

If p is prime and p ∤ a, then a^(p−1) ≡ 1 (mod p). Equivalently, a^p ≡ a (mod p).

Explanation

Fermat's Little Theorem is an important result connecting prime numbers with modular exponentiation. If p is a prime number and a is an integer not divisible by p, then a^(p−1) ≡ 1 (mod p). An equivalent form states that a^p ≡ a (mod p) for every integer a. The theorem provides a powerful way to simplify large powers modulo a prime. For example, when calculating a^k modulo p, the exponent can often be reduced using the fact that a^(p−1) is congruent to 1 when p does not divide a. The theorem is also used in primality testing, modular inverse calculations, and cryptography. However, satisfying the theorem's congruence condition does not always prove that a number is prime, because some composite numbers can also satisfy related conditions for particular bases.

Variables

A

An integer base.

P

A prime number used as the modulus.

P − 1

The exponent appearing in the nonzero-residue form.

P ∤ a

The statement that p does not divide a.

Example or application

Problem

Verify Fermat's Little Theorem for a = 2 and p = 7.

Solution

Since 7 is prime and does not divide 2, the theorem applies. Calculate 2^(7−1) = 2^6 = 64. Since 64 = 9 × 7 + 1, we obtain 64 ≡ 1 (mod 7).

Answer

2^6 ≡ 1 (mod 7)

Text

Fermat's Little Theorem applies to a prime modulus. Its nonzero-residue form gives a^(p−1) ≡ 1 (mod p), while its equivalent general form gives a^p ≡ a (mod p) for every integer a.

Key Points

  • The modulus p must be prime.

  • The nonzero-residue form requires p not to divide a.

  • The expression a^(p−1) is congruent to 1 modulo p under the theorem's conditions.

  • The equivalent form a^p ≡ a (mod p) holds for every integer a when p is prime.

  • The theorem helps simplify large modular powers.

  • The theorem can support primality testing but does not by itself guarantee primality.

Applications

  • Simplifying large powers modulo prime numbers.

  • Finding modular inverses.

  • Developing primality tests.

  • Cryptographic algorithms.

  • Solving number-theoretic congruences.

Learning Outcomes

  • State Fermat's Little Theorem.

  • Identify the conditions required to apply it.

  • Use the theorem to simplify modular exponentiation.

  • Explain why the theorem alone cannot prove that every tested number is prime.

Practice Questions

  • Verify Fermat's Little Theorem for a = 3 and p = 5.

  • Calculate 2^10 modulo 11 using the theorem.

  • Find 3^20 modulo 7.

  • Explain why the condition p ∤ a matters in the nonzero-residue form.

  • Distinguish Fermat's Little Theorem from Fermat's Last Theorem.

Related Concepts

  • Prime Numbers

  • Modular Exponentiation

  • Euler's Theorem

  • Modular Inverses

  • Primality Testing

Common Mistakes

  • Applying the theorem with a composite modulus.

  • Using the nonzero-residue form when p divides a.

  • Confusing Fermat's Little Theorem with Fermat's Last Theorem.

  • Assuming that a number satisfying a Fermat congruence must be prime.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Kenneth H. Rosen, Elementary Number Theory and Its Applications
  • David M. Burton, Elementary Number Theory

Suggest a correction or source · More in Arithmetic & Number Theory