Fermat Little Theorem Calculator

Calculator Inputs

Residue Graph

The graph plots k against a^k mod modulus.

Example Data Table

Formula Used

Fermat Little Theorem:

a^(p - 1) ≡ 1 mod p

This works when p is prime and gcd(a, p) = 1.

Power reduction:

a^n mod p = a^(n mod (p - 1)) mod p

Modular inverse:

a^(-1) mod p = a^(p - 2) mod p

Generic modular power:

a^n mod m is calculated using binary modular exponentiation.

How to Use This Calculator

1. Select a calculation mode.
2. Enter the base value a.
3. Enter the exponent n when using power modes.
4. Enter a prime modulus p for theorem and inverse modes.
5. Use generic mode when the modulus is not prime.
6. Choose how many graph points to display.
7. Press Calculate.
8. Review the result, steps, notes, and graph.
9. Use CSV or PDF export for records.

Article: Understanding Fermat Little Theorem

Why the Theorem Matters

Fermat Little Theorem gives a fast way to handle modular powers. It is useful when a base is large. It also helps when the exponent is huge. The theorem applies under two key conditions. The modulus p must be prime. The base a must not divide evenly by p. Then a^(p - 1) leaves remainder 1.

Reducing Large Powers

This result saves many repeated multiplications. You can reduce the exponent before calculating. For a^n mod p, use n mod (p - 1). This works only when gcd(a, p) equals 1. The calculator checks those conditions first. It then explains whether reduction is allowed.

Finding Inverses

The tool also finds modular inverses. In modular arithmetic, an inverse is a special number. It turns multiplication into a remainder of 1. For a prime modulus, the inverse is a^(p - 2) mod p. This shortcut appears in cryptography and coding contests. It is also common in discrete mathematics.

Checking Validity

The prime test helps avoid wrong use. Fermat shortcuts can fail with composite moduli. A composite modulus may pass a simple check. So the page reports the modulus status. It also reports the greatest common divisor. You see the reduced exponent and final remainder. You also get notes about validity.

Reading the Graph

The graph plots powers against their residues. It helps you see cycles. Residue patterns repeat under a prime modulus. These cycles explain why exponent reduction works. They also help students understand modular periods.

Practical Example

Use small examples first. Try base 7, exponent 128, and modulus 13. Then compare the reduced exponent with the original exponent. The result remains the same. The exponent is reduced modulo 12. This makes the work shorter. It also makes the answer easier to verify.

Advanced Use

For advanced work, use generic power mode. It calculates a^n mod m without prime assumptions. Then use theorem mode for a prime modulus. Comparing both modes builds confidence. It also shows when the theorem is valid.

Final Notes

This calculator supports learning, homework, and reports. It keeps each step visible. It exports results for later review. The formulas and table make the method reusable. Careful inputs make the final answer easier to audit later. Saved exports support sharing with classmates and tutors.

FAQs