MathematicsNumber TheoryUniversity

OCRAPOntarioNSWCBSEGCE O-LevelMoECAPS

Fermat's Little Theorem

States that a^{p-1} ≡ 1 (mod p) for any prime p and integer a not divisible by p.

Understand the formulaSee the free derivationOpen the full walkthrough

a^{p - 1} \equiv 1 (mod p)

Open Full Walkthrough Try Calculator

This public page keeps the free explanation visible and leaves premium worked solving, advanced walkthroughs, and saved study tools inside the app.

Core idea

Overview

Fermat's Little Theorem establishes a fundamental relationship between prime numbers and modular arithmetic, stating that for any prime p and integer a not divisible by p, the value a raised to the power of p-1 is congruent to 1 modulo p. It serves as a foundational building block for group theory and modern computational mathematics.

When to use: This theorem is applicable when simplifying modular exponentiation problems where the modulus is a prime number. It requires the base to be coprime to the modulus, meaning the base cannot be a multiple of the prime.

Why it matters: It is the mathematical foundation for the RSA encryption algorithm and various primality tests used in cybersecurity. By allowing large exponents to be reduced efficiently, it enables secure digital communication and data integrity across global networks.

Symbols

Variables

R = Remainder, a = Integer Base, p = Prime Modulus

R

Remainder

V a r iab l e

a

Integer Base

V a r iab l e

p

Prime Modulus

V a r iab l e

Walkthrough

Derivation

Derivation/Understanding of Fermat's Little Theorem

This derivation uses properties of modular arithmetic and prime numbers to show that for any integer 'a' not divisible by a prime 'p', a^{p-1} is congruent to 1 modulo p.

p is a prime number.
a is an integer such that p does not divide a (i.e., gcd(a, p) = 1).

Define the set of non-zero residues:

This set contains all integers from 1 to p-1, which represent all non-zero residues modulo p. These are the elements that are coprime to p.

S = {1, 2, \dots, p - 1}

Consider the set of multiples of 'a':

Since p is prime and a is not a multiple of p, each element in S' is distinct and non-zero modulo p. Therefore, S' is simply a permutation of S modulo p.

S^{'} = {a \cdot 1, a \cdot 2, \dots, a \cdot (p - 1)} (mod p)

Equate the products of elements in S and S':

Because S' is a permutation of S modulo p, the product of their elements must be congruent modulo p. The product of elements in S is (p-1)!.

k = 1 \prod p - 1 k \equiv k = 1 \prod p - 1 (ak) (mod p)

Simplify the congruence:

We can factor out a^{p-1} from the right side. Since p is prime, (p-1)! is not divisible by p, meaning gcd((p-1)!, p) = 1. Thus, we can divide both sides by (p-1)! modulo p, leading to the theorem.

(p - 1)! \equiv a^{p - 1} (p - 1)! (mod p)

Result

(p - 1)! \equiv a^{p - 1} (p - 1)! (mod p)

Source: Elementary Number Theory and Its Applications by Kenneth Rosen

Visual intuition

Graph

The graph appears as a constant horizontal line at a value of 1 on the Y-axis for all valid integer values of the independent variable on the X-axis. This occurs because the modular arithmetic relationship forces the remainder to remain fixed at 1 whenever the base is not divisible by the prime modulus.

Graph type: constant

Why it behaves this way

Intuition

Imagine numbers arranged in a circle of 'p' positions; repeatedly multiplying an integer 'a' (not a multiple of 'p') by itself 'p-1' times will always land you back at the '1' position on this circle.

a

The integer base being exponentiated.

This is the number whose powers we are observing; it must not share any prime factors with 'p' for the theorem to apply.

p

The prime number acting as the modulus.

This prime number defines the arithmetic 'universe' where numbers cycle after 'p'; its primality is essential for the theorem.

p - 1

The specific exponent to which the base 'a' is raised.

This exponent, one less than the prime modulus, represents the 'full cycle' length for powers of 'a' in the multiplicative group modulo 'p', bringing 'a' back to 1.

\equiv 1 (mod p)

The congruence relation stating that a^(p-1) and 1 have the same remainder when divided by p.

This means that within the modular arithmetic system defined by 'p', a^(p-1) behaves identically to '1'.

Free study cues

Insight

Canonical usage

Fermat's Little Theorem is used in number theory and cryptography with dimensionless integers and prime numbers.

Common confusion

Attempting to apply the theorem when the modulus p is composite or when the base a is a multiple of p.

Dimension note

This theorem describes properties of the ring of integers modulo p. All terms are pure numbers without physical dimensions.

Unit systems

$a$ dimensionless · An integer base that must be coprime to the modulus p.

$p$ dimensionless · A prime number serving as the modulus.

One free problem

Practice Problem

Calculate the remainder (result) when 8¹² is divided by the prime number 13.

Integer Base8

Prime Modulus13

Solve for: result

Hint: Check if the exponent is equal to p - 1.

The full worked solution stays in the interactive walkthrough.

Where it shows up

Real-World Context

Used in the Miller-Rabin primality test to determine if a large number is likely prime by checking if the theorem holds for random bases.

Study smarter

Tips

Verify that p is a prime number before applying the identity.
Check that the base a is not divisible by p to ensure the residue is 1.
Use the property aᵏ ≡ a^(k mod p-1) (mod p) to handle exponents much larger than p-1.

Avoid these traps

Common Mistakes

Applying the theorem to composite numbers (use Euler's Totient Theorem instead).
Forgetting that a and p must be coprime.

Common questions

Frequently Asked Questions

This derivation uses properties of modular arithmetic and prime numbers to show that for any integer 'a' not divisible by a prime 'p', a^{p-1} is congruent to 1 modulo p.

This theorem is applicable when simplifying modular exponentiation problems where the modulus is a prime number. It requires the base to be coprime to the modulus, meaning the base cannot be a multiple of the prime.

It is the mathematical foundation for the RSA encryption algorithm and various primality tests used in cybersecurity. By allowing large exponents to be reduced efficiently, it enables secure digital communication and data integrity across global networks.

Applying the theorem to composite numbers (use Euler's Totient Theorem instead). Forgetting that a and p must be coprime.