Fermat's Little Theorem Calculator – Guide & Formulas
Calculate a^p mod p using Fermat's Little Theorem. Verify primality, compute modular inverses, and solve exponentiation problems for prime moduli instantly.
Apply Fermat's Little Theorem to compute modular exponentiation and verify primality. Enter any base and prime modulus to instantly calculate a^p mod p and its modular inverse.
Key Takeaway
Use the free Fermat's Little Theorem Calculator to calculate a^p mod p using fermat's little theorem. verify primality, compute modular inverses, and solve exponentiation problems for prime moduli instantly. Get instant results with step-by-step explanations.
How to Use the Fermat's Little Theorem Calculator
- Enter the base value (a) — any positive integer.
- Enter the exponent (p) — must be a prime number for the theorem to apply.
- Review the computed result of a^p mod p.
- Check the modular inverse of a mod p using the theorem.
- Use the primality hint to verify whether p is prime.
The Formula
Variable Definitions
- a: The base integer (any positive integer coprime to p)
- p: A prime modulus (must be prime for the theorem to hold)
- ≡: Congruence relation (two expressions have the same remainder when divided by p)
- mod p: Modular arithmetic — the remainder when divided by p
- a^(-1): The modular multiplicative inverse of a modulo p — a value such that a × a^(-1) ≡ 1 (mod p)
Computing 3^5 mod 5 and Modular Inverse
Apply Fermat's Little Theorem to compute 3^5 mod 5 and find the modular inverse of 3 mod 5.
- Step 1: Identify inputs. a = 3, p = 5 (which is prime).
- Step 2: Compute 3^5 = 243.
- Step 3: Divide 243 by 5: 243 = 48 × 5 + 3. So 3^5 mod 5 = 3.
- Step 4: By Fermat's theorem, a^p ≡ a (mod p), so 3^5 mod 5 = 3. ✓
- Step 5: For the modular inverse: 3^(5-2) = 3^3 = 27. 27 mod 5 = 2. So 3^(-1) mod 5 = 2.
- Step 6: Verify: 3 × 2 = 6, and 6 mod 5 = 1. ✓ The modular inverse is 2.
Frequently Asked Questions
What is Fermat's Little Theorem?
Fermat's Little Theorem states that if p is a prime number and a is an integer not divisible by p, then a^(p-1) ≡ 1 (mod p). Equivalently, a^p ≡ a (mod p) for any integer a. This is a fundamental result in number theory with applications in cryptography and primality testing.
When does Fermat's Little Theorem fail?
The theorem holds only when p is prime. If p is composite (not prime), the congruence a^(p-1) ≡ 1 (mod p) may still hold for some values of a, but not all. Numbers that pass the Fermat test for all bases coprime to n are called Carmichael numbers — they are composite but fool the basic Fermat primality test.
How do I find the modular inverse using this theorem?
If p is prime and gcd(a,p) = 1, then the modular inverse of a modulo p is a^(p-2) mod p. This follows from a^(p-1) ≡ 1 (mod p), which means a × a^(p-2) ≡ 1 (mod p). So a^(p-2) is the multiplicative inverse of a modulo p.
What is a modular inverse?
The modular inverse of a modulo m is an integer x such that a × x ≡ 1 (mod m). It exists only when gcd(a,m) = 1. For example, the modular inverse of 3 mod 7 is 5, because 3 × 5 = 15 ≡ 1 (mod 7).
How does Fermat's Little Theorem relate to RSA cryptography?
RSA encryption uses modular exponentiation and relies on the difficulty of factoring large numbers. Fermat's Little Theorem (and its generalization, Euler's theorem) ensures that decryption works correctly: encrypting with exponent e and decrypting with exponent d = e^(-1) mod (p-1)(q-1) recovers the original message because m^(ed) ≡ m (mod n).
Can this calculator check if a number is prime?
This calculator uses Fermat's Little Theorem as a heuristic primality test. If a^(p-1) mod p ≠ 1 for some base a coprime to p, then p is definitely composite. However, passing the test for one base does not guarantee primality — Carmichael numbers can fool the test. For definitive primality, use the Miller-Rabin test.
What is the difference between Fermat's Little Theorem and Euler's Theorem?
Fermat's Little Theorem applies specifically when the modulus p is prime: a^(p-1) ≡ 1 (mod p). Euler's Theorem is the generalization: a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function (count of integers from 1 to n coprime to n). When n is prime, φ(n) = n-1, so Euler's Theorem reduces to Fermat's.
What is the practical use of Fermat's Little Theorem?
Applications include: (1) Fast modular exponentiation in cryptography, (2) Primality testing (Fermat test), (3) Computing modular inverses efficiently, (4) Simplifying number theory problems, (5) RSA key generation and encryption/decryption operations.
How do I compute a^b mod m efficiently for large exponents?
Use modular exponentiation (repeated squaring). Instead of computing a^b directly and then taking mod m (which creates enormous numbers), repeatedly square and multiply while taking mod m at each step. For example, 3^13 mod 7: 3^1 = 3, 3^2 = 2, 3^4 = 4, 3^8 = 2, then 3^13 = 3^8 × 3^4 × 3^1 = 2 × 4 × 3 = 24 mod 7 = 3.
What are Carmichael numbers?
Carmichael numbers are composite numbers n that satisfy a^(n-1) ≡ 1 (mod n) for all integers a coprime to n. They are 'absolute Fermat pseudoprimes' that fool the Fermat primality test. The smallest Carmichael number is 561 = 3 × 11 × 17. There are infinitely many, and they become more common as numbers get larger.