The Fermat's Little Theorem calculator provided by Hesapstan explains theorem checking, power reduction, and modular inverse calculations under a prime modulus step by step.
Fermat's Little Theorem describes powers modulo a prime
Fermat's Little Theorem says that if p is prime and a is relatively prime to p, then a^(p−1) ≡ 1 (mod p). An equivalent form often used for checking is a^p ≡ a (mod p).
The theorem is useful when the exponent is large. Instead of expanding a huge power directly, you can use the repeating structure created by the prime modulus.
Fermat's Little Theorem is a modular arithmetic theorem that explains how powers repeat when the modulus is prime.
The calculator supports three Fermat theorem tasks
In theorem check mode, the calculator compares a^p mod p with a mod p. The modulus p must be prime; otherwise the input does not match the theorem's condition.
In power reduction mode, it computes a^n mod p using the Fermat cycle. In modular inverse mode, it computes a^(-1) mod p as a^(p−2) mod p.
The calculator does not generate RSA keys, perform encryption, or make security claims. It is an educational modular arithmetic tool for the three supported Fermat theorem modes.
The modulus must be prime for this theorem
The standard theorem is stated for a prime modulus p. A calculation modulo 7 fits this condition; a calculation modulo 8 or 9 does not automatically follow the same rule.
The form a^(p−1) ≡ 1 (mod p) also requires gcd(a, p) = 1. If a is a multiple of p, the result should be interpreted through the correct theorem condition rather than by applying the inverse rule blindly.
The runtime validates p as prime to protect the theorem's scope. That validation does not turn the page into a general-purpose primality testing tool.
Power reduction uses the p−1 cycle
When p is prime and a is not divisible by p, Fermat's Little Theorem gives a^(p−1) ≡ 1 (mod p). That lets the exponent be reduced modulo p−1.
For example, to find 2^100 mod 7, use p−1 = 6. Since 100 leaves remainder 4 when divided by 6, the problem reduces to 2^4 mod 7.
This page does not implement Euler's theorem for non-prime moduli or a general modular exponent theory. The content follows the prime-modulus contract only.
The modular inverse is found with a^(p−2)
A modular inverse of a modulo p is a number x such that a × x ≡ 1 (mod p). If p is prime and a is not divisible by p, Fermat's Little Theorem gives x ≡ a^(p−2) (mod p).
For example, the inverse of 3 modulo 7 is found by 3^(7−2) = 3^5. Since 3^5 mod 7 = 5, the inverse is 5. Check: 3 × 5 = 15, and 15 mod 7 = 1.
The ordinary reciprocal of 3 is 1/3. The modular inverse of 3 modulo 7 is 5 because it makes the product congruent to 1 modulo 7.
Examples separate checking, power reduction, and inverse calculation
Theorem check: with a = 3 and p = 7, 3^7 mod 7 = 3, so the form a^p ≡ a (mod p) is verified.
Power reduction: 2^100 mod 7 uses 100 ≡ 4 (mod 6), so 2^100 ≡ 2^4 ≡ 16 ≡ 2 (mod 7).
Modular inverse: 3^5 mod 7 = 5, so 5 is the inverse of 3 modulo 7.
Frequently Asked Questions
What is Fermat's Little Theorem?
If p is prime and gcd(a, p) = 1, then a^(p−1) ≡ 1 (mod p). A related form is a^p ≡ a (mod p).
Why must p be prime?
The theorem used by this calculator is the prime-modulus version. Non-prime moduli require different tools, such as Euler's theorem.
What is a modular inverse?
A modular inverse of a modulo p is a value x such that a × x leaves remainder 1 when divided by p.
Is a modular inverse the same as a reciprocal?
No. A reciprocal is 1/a in ordinary arithmetic. A modular inverse is an integer residue that multiplies with a to give 1 modulo p.
Does this calculator test primality in general?
No. It validates the modulus for the supported theorem calculation, but it is not a Miller-Rabin or general primality-testing calculator.
Can this calculator be used for RSA?
No. It does not generate keys, encrypt messages, or provide cryptographic security analysis.