Fermat's Little Theorem Calculator
States that a^{p-1} ≡ 1 (mod p) for any prime p and integer a not divisible by p.
Formula first
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.
Symbols
Variables
R = Remainder, a = Integer Base, p = Prime Modulus
Apply it well
When To Use
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.
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.
One free problem
Practice Problem
Calculate the remainder (result) when 8¹² is divided by the prime number 13.
Solve for:
Hint: Check if the exponent is equal to p - 1.
The full worked solution stays in the interactive walkthrough.
References
Sources
- Wikipedia: Fermat's Little Theorem
- Britannica
- Hardy and Wright, An Introduction to the Theory of Numbers
- Discrete Mathematics and Its Applications by Kenneth H. Rosen
- Elementary Number Theory and Its Applications by Kenneth Rosen