Fermats Little Theorem Calculator - a^(p-1) mod p verifier and modular exponent shortcut
Fermats little theorem calculator to verify a^(p-1) mod p = 1, reduce a^k mod p using the FLT shortcut, and confirm whether p is prime.
Fermats Little Theorem Calculator
Results
What Is the Fermats Little Theorem Calculator?
The fermats little theorem calculator verifies Fermat's identity a^(p-1) ≡ 1 (mod p) for any prime p and base a that is coprime with p, and uses the same identity as a shortcut to shrink huge modular exponents a^k mod p into a^(k mod p-1) mod p without ever computing the full power.
- • Cryptography homework: Verify the FLT identity used in Diffie-Hellman and RSA key generation without expanding a huge power by hand.
- • Fermat primality testing: Test whether a number is probably prime by checking that a^(p-1) mod p returns 1 for several witness bases.
- • Modular exponent shortcut: Reduce a^k mod p to a^(k mod p-1) mod p when p is prime so that 2^1000 mod 7 becomes a tiny exponent in seconds.
- • Finding multiplicative order: Compute the smallest n with a^n ≡ 1 (mod p) to study cyclic groups and discrete logarithm problems.
Fermat's little theorem is the foundation of fast modular exponentiation, which is the engine behind RSA signatures and discrete-log key exchange. The identity holds only when p is a prime and gcd(a, p) = 1, so the calculator runs a primality test on p and an Euclidean gcd check before claiming the shortcut is valid.
The same identity is the cleanest worked example of a multiplicative group of order p-1, and it is also a one-line reduction that turns unmanageable powers into single-digit arithmetic. This tool shows both views: the FLT check a^(p-1) mod p and the exponent-reduction shortcut a^k mod p = a^(k mod p-1) mod p.
If you only need the bare remainder a mod n without the FLT shortcut, the Modulo Calculator gives the same modular arithmetic primitives for any modulus.
How the Fermats Little Theorem Formula Works
The calculator takes three integers a, p, and k and applies Fermat's little theorem in two directions: it computes a^(p-1) mod p to confirm the FLT identity, and it reduces a^k mod p to a^(k mod p-1) mod p using the same theorem when its conditions are met.
- a: Integer base. Negative values are first reduced mod p so that -3 mod 7 becomes 4.
- p: Modulus, which must be prime for FLT to apply. The calculator verifies primality by trial division up to sqrt(p).
- k: Non-negative exponent for a^k mod p. The calculator also shows k mod p-1 as the simplified FLT exponent.
- gcd(a, p): Greatest common divisor. FLT only applies when gcd(a, p) = 1; otherwise a is a multiple of p and a^k mod p collapses to 0.
Fast modular exponentiation (square-and-multiply) keeps the intermediate products inside JavaScript's BigInt range, so even k up to 10^12 finishes in milliseconds. The calculator then confirms FLT by computing a^(p-1) mod p independently, which is exactly the Fermat primality check.
If p turns out to be composite, the calculator does not silently apply the shortcut. It shows the FLT remainder (which is rarely 1), keeps k mod p-1 for reference, and sets a Fermat-applies flag to false so you can see which branch is in play.
Worked example: 2^100 mod 7
a = 2, p = 7, k = 100
p is prime and gcd(2, 7) = 1, so FLT applies. The shortcut replaces 2^100 mod 7 with 2^(100 mod 6) mod 7 = 2^4 mod 7 = 16 mod 7.
2^100 mod 7 = 2 (and 2^(p-1) mod 7 = 1 confirms the FLT identity).
The exponent dropped from 100 to 4 with no loss of correctness because the multiplicative group mod 7 has order 6.
According to Wolfram MathWorld, Fermat's little theorem states that if p is prime and a is an integer not divisible by p, then a^(p-1) is congruent to 1 modulo p, and the corollary a^k mod p = a^(k mod p-1) mod p follows directly.
When you want a deeper primality view that goes beyond trial division, the Prime Number Checker handles larger ranges and explains why FLT is the basis of probable-prime tests.
Key Concepts Behind Fermat's Little Theorem
These four concepts are the building blocks of the calculator: each one explains a number or flag the result panel reports so you can interpret the output the way a number theorist would.
Prime modulus p
Fermat's little theorem requires p to be a prime. The calculator confirms primality with deterministic trial division up to sqrt(p), which is enough for p <= 100,000 and matches the result a^(p-1) mod p should give if FLT is in play.
Coprime base gcd(a, p) = 1
When gcd(a, p) = 1, the base a sits inside the multiplicative group of integers mod p, which has exactly p-1 elements. That cyclic group is what makes the exponent-reduction shortcut work; without this condition the theorem does not apply.
Reduced exponent k mod p-1
Because the multiplicative group has order p-1, every exponent k behaves the same as k mod p-1. The calculator surfaces this simplified exponent so you can see why a^100 mod 7 collapses to a^4 mod 7 with no extra arithmetic.
Multiplicative order of a
The order of a mod p is the smallest positive integer n such that a^n ≡ 1 (mod p). It always divides p-1, and the calculator reports it as a side benefit whenever FLT applies, which is useful in discrete-log work.
These four concepts also explain the two flags at the bottom of the result panel. 'p is prime' tells you whether the FLT conditions are even possible, and 'FLT applies' combines that with the coprime check to decide whether the shortcut is mathematically safe.
Whenever the result panel reports a gcd greater than 1, the Relatively Prime Calculator explains why that case forces FLT to fail and shows related coprime checks.
How to Use the Fermats Little Theorem Calculator
The calculator turns a triple (a, p, k) into a verified FLT result plus the exponent-reduction shortcut in real time. Follow these five steps to read the result panel without re-reading the math.
- 1 Enter the base a: Type any integer into the Base (a) field. Negative values are accepted and are first reduced modulo p so that -3 mod 7 becomes 4 internally.
- 2 Enter the prime modulus p: Type a candidate prime into the Prime modulus (p) field. The calculator runs a trial-division primality check before applying FLT and surfaces the result in the 'p is prime' flag.
- 3 Enter the exponent k: Type the exponent you want to reduce, from 0 up to 10^12. The calculator shows k mod p-1 alongside the full result so you can see the shortcut at work.
- 4 Read the FLT check and the FLT flag: Look at a^(p-1) mod p first. When it equals 1 and the FLT-applies flag is set, the shortcut a^k mod p = a^(k mod p-1) mod p is valid for your inputs.
- 5 Use the result: Take a^k mod p for cryptography or homework, or copy the simplified exponent for an explanation that fits on a single line.
Try a = 3, p = 11, k = 125: the calculator returns a^k mod p = 1, FLT check = 1, simplified exponent = 5, and order = 5, because 3^5 ≡ 1 (mod 11) and 125 mod 10 = 5.
When you need to combine several FLT-style congruences for different primes at once, the Chinese Remainder Calculator walks through the same kind of modular arithmetic across multiple moduli.
Benefits of Using This Fermats Little Theorem Calculator
Compared with hand-rolling the FLT identity, the calculator gives four concrete advantages that show up in homework and cryptography code.
- • Verifies the identity, not just the power: It reports a^(p-1) mod p alongside a^k mod p, so you can see in one glance whether FLT actually holds for your inputs.
- • Reduces huge exponents safely: Square-and-multiply with BigInt keeps intermediate products in range, so k up to 10^12 finishes in milliseconds without losing precision.
- • Detects the failure modes: It explicitly tests gcd(a, p) and primality of p, then sets the FLT-applies flag so you never use the shortcut on a composite modulus by accident.
- • Surfaces the multiplicative order: It reports the smallest n with a^n ≡ 1 (mod p), which is the data you need for discrete-log work and cyclic group studies.
- • Works for negative bases: Negative a values are reduced mod p before any multiplication, so the result panel always shows the canonical representative in [0, p-1].
Because RSA encryption relies on FLT for both key generation and decryption, the RSA Calculator shows how this identity feeds into a full RSA workflow once you have picked your primes.
Factors That Affect the Fermat Result
Three numbers decide whether FLT gives a clean answer or a flagged exception. Two are inputs, and one is a property of the chosen prime.
Whether p is prime
If p is composite, FLT does not apply. The calculator still computes a^k mod p with square-and-multiply, but the FLT remainder a^(p-1) mod p is generally not 1, and the FLT-applies flag is false.
Coprimality of a and p
When gcd(a, p) > 1, the base is a multiple of p and a^k mod p drops to 0 for any positive k. The gcd check at the top of the result panel tells you this without re-reading the identity.
Size of the exponent k
Larger k values exercise the square-and-multiply path more heavily, but the FLT shortcut keeps the displayed exponent at k mod p-1 regardless of how big k is, so the result is always a number in [0, p-1].
- • The deterministic trial-division primality test is fast for p <= 100,000 but does not scale to RSA-sized primes; for those use a probabilistic primality test such as Miller-Rabin.
- • When FLT does not apply because p is composite, the simplified exponent k mod p-1 is still shown for reference but should not be used as a shortcut; Carmichael's lambda function or Euler's totient is the right substitute.
- • JavaScript's BigInt arithmetic is exact for these ranges, so the result is always an integer; do not paste the displayed exponent into a floating-point context where it would round.
These limitations are why the calculator keeps two rows in the result panel. The full a^k mod p result is trustworthy because it uses square-and-multiply with BigInt, while the simplified exponent and FLT remainder are only safe when the two flags say the shortcut applies.
As published by Wikipedia (Fermat's little theorem), Fermat's little theorem is the basis for the Fermat primality test and for computing a^k mod p by reducing the exponent k modulo (p-1) when p is prime.
According to Khan Academy, Fermat's little theorem lets you find the remainder of a huge power of an integer when divided by a prime by reducing the exponent modulo p-1.
When a is negative and you want to see the floored versus truncated remainder interpretation, the Modulo Of Negative Numbers shows how the same modular reduction behaves across programming conventions.
Frequently Asked Questions
Q: What is Fermat's little theorem in simple terms?
A: Fermat's little theorem says that for any prime modulus p and any base a that is not a multiple of p, the value a^(p-1) leaves a remainder of 1 when divided by p. That single identity is what powers most of modern public-key cryptography and lets large modular exponents collapse to tiny ones.
Q: How do you use Fermat's little theorem to compute a^k mod p?
A: Reduce the exponent k modulo (p-1) and replace a^k mod p with a^(k mod (p-1)) mod p. For example, 2^100 mod 7 becomes 2^(100 mod 6) = 2^4 mod 7 = 2, because 2^6 ≡ 1 (mod 7). The same trick is what this calculator applies when FLT applies.
Q: What are the conditions required for Fermat's little theorem to apply?
A: Fermat's little theorem needs two conditions: p must be a prime number, and gcd(a, p) must equal 1, which means a must not be a multiple of p. If either condition fails, a^(p-1) mod p is not guaranteed to equal 1 and the shortcut a^k mod p = a^(k mod (p-1)) mod p no longer holds.
Q: What happens when a and p share a common factor?
A: If gcd(a, p) is greater than 1, then p divides some power of a and the result a^k mod p can drop to 0. For example, 6^3 mod 9 = 0 because gcd(6, 9) = 3, not 1. The calculator reports gcd(a, p) and flags that FLT does not apply in this situation.
Q: How is Fermat's little theorem used in cryptography?
A: Diffie-Hellman key exchange and RSA key generation both rest on Fermat's little theorem and its generalization, Euler's theorem. The shortcut a^k mod p = a^(k mod (p-1)) mod p lets a program raise a base to a 2048-bit exponent in milliseconds by reducing the exponent modulo p-1 first, which is the heart of fast modular exponentiation.
Q: What is the difference between Fermat's little theorem and Euler's theorem?
A: Fermat's little theorem requires the modulus p to be prime and uses the exponent p-1, while Euler's theorem works for any modulus n that is coprime with a and uses Euler's totient phi(n) instead of p-1. Fermat's little theorem is the special case of Euler's theorem when n = p is prime, so phi(p) = p-1.