How to Use Fermat’s Little Theorem Calculator
The Fermat’s Little Theorem Calculator computes a^n mod p with optional exponent reduction. Fill in three integer fields and read the remainder and calculation steps.
- Enter the base a - Any integer (positive or negative).
- Enter the exponent n - A non-negative integer. Large values like 10^15 work instantly.
- Enter the modulus p - A positive integer ≥ 2. Prime values enable the full Fermat simplification.
- Read the result - The Fermat’s Little Theorem Calculator checks primality, checks coprimality, reduces the exponent when possible, and shows the final remainder.
For example, entering a = 3, n = 100, p = 7 gives: 100 mod 6 = 4, so 3^100 mod 7 = 3^4 mod 7 = 81 mod 7 = 4.
Formula & Theory - Fermat’s Little Theorem Calculator
The Fermat’s Little Theorem Calculator is based on:
If p is prime and gcd(a, p) = 1:
a^(p−1) ≡ 1 (mod p)
Equivalent form:
a^p ≡ a (mod p)
Exponent reduction:
a^n mod p = a^(n mod (p−1)) mod p| Symbol | Meaning |
|---|---|
| a | Base integer |
| n | Exponent |
| p | Prime modulus |
| p−1 | Euler’s totient for prime p (equals φ(p)) |
| n mod (p−1) | Reduced exponent used in the computation |
Why exponent reduction works: Because a^(p−1) ≡ 1, multiplying by a^(p−1) leaves the result unchanged. So any multiple of (p−1) in the exponent cancels out, and only the remainder n mod (p−1) matters.
When Fermat does not apply: If p is not prime, or if p divides a (making gcd(a, p) > 1), the theorem cannot be used directly. The calculator then uses the square-and-multiply algorithm directly.
Assumptions and Limits
The modulus p must be at least 2. The exponent n must be non-negative. All inputs must be integers.
Use Cases for Fermat’s Little Theorem Calculator
The Fermat’s Little Theorem Calculator is used in number theory, cryptography, and competitive mathematics. Common uses include:
- Number theory coursework - Verify that 2^12 mod 13 = 1 using the theorem and confirm with the calculator.
- RSA cryptography - Understand the mathematical basis of public-key encryption, where Fermat’s theorem underlies key generation.
- Competitive mathematics - Quickly evaluate large modular powers that appear in olympiad problems.
- Primality intuition - Test whether a^(p-1) mod p = 1 for several bases as a heuristic primality test (Fermat primality test).
The Fermat’s Little Theorem Calculator shows every step — primality check, coprimality check, exponent reduction — making it an ideal tool for understanding the theorem rather than just getting an answer.