What Is Fermat’s Little Theorem?

Fermat’s little theorem states that if p is a prime number and a is an integer, then a^p ≡ a (mod p). If a and p are coprime (their greatest common divisor is 1), it also says a^(p-1) ≡ 1 (mod p). This “little” label distinguishes it from Fermat’s last theorem, a tougher problem proved in 1995. Understanding this theorem is key for modular arithmetic, primality tests, and more.

• Why “Little”? It’s simpler than the “great” last theorem, which deals with equations like x^n + y^n = z^n for n>2.
• History: Pierre de Fermat stated it in 1640, but Leonhard Euler proved it in 1736. Leibniz had an unpublished proof earlier.

How to Use the Fermat’s Little Theorem Calculator

This calculator is easy to use, even if you’re new to number theory. Follow these steps:

• Input Values: Enter integer a and prime p in the fields provided.
• Check Primality: The tool verifies if p is prime. If not, it shows an error.
• Get Results: It computes a^p mod p and, if coprime, a^(p-1) mod p, displaying the outcome.

Example Inputs:

If you enter invalid data (e.g., p=9, not prime), it warns: “Error: p is not a prime number.”

Verifying the Theorem with Examples

Let’s walk through some examples to see how it works.

Example 1: Coprime Case

• Inputs: a = 3, p = 5
• Calculation: Since gcd(3,5)=1, 3^4 ≡ 1 (mod 5). Check: 81 mod 5 = 1.
• Calculator Output: “Yay, 3^4 ≡ 1 (mod 5) holds.”

Example 2: Non-Coprime Case

• Inputs: a = 10, p = 5
• Calculation: gcd(10,5)=5, so 10^5 ≡ 10 (mod 5). Both sides = 0 mod 5.
• Calculator Output: “Note: 10 and 5 are not coprime, 10^5 ≡ 10 (mod 5).”

Example 3: Large Numbers

• Inputs: a = 7, p = 11
• Calculation: gcd(7,11)=1, so 7^10 ≡ 1 (mod 11). The tool uses efficient methods to compute this.
• Calculator Output: “7^10 ≡ 1 (mod 11) holds.”

Handling Errors and Edge Cases

The calculator catches mistakes to keep your work accurate.

• Non-Prime p: If p=9, it says, “Error: p is not a prime number.”
• Invalid Input: Letters or decimals trigger, “Error: a must be an integer, p must be a positive integer.”
• Negative a: For a=-2, p=5, it reduces -2 to 3 mod 5 and proceeds.

This ensures you don’t waste time on wrong inputs.

Using Fermat’s Little Theorem for Primality Testing

You can test if p is prime using this theorem. Here’s how:

1. Pick a random a from 2 to p-2.
2. Compute a^(p-1) mod p.
3. If not 1, p is composite. If 1, try another a.

Example: Test p=13 with a=3.

• 3^12 mod 13 = 1 (via successive squaring).
• Try a=5: 5^12 mod 13 = 1.
• Likely prime, but repeat for certainty.

Caution: Composites like 341 (11*31) pass for a=2. Use multiple a or other tests for reliability.

Finding Multiplicative Inverses

The theorem helps find the inverse of a mod p when gcd(a,p)=1. The inverse b satisfies a*b ≡ 1 (mod p).

• Method: From a^(p-1) ≡ 1, multiply by a^(p-2): a * a^(p-2) ≡ 1.
• Inverse: a^(p-2) mod p.

Example: a=3, p=7.

• Inverse = 3^5 mod 7.
• 3^2=2, 3^4=4, 3^5=12 mod 7=5.
• Check: 3*5=15 mod 7=1.

The calculator can compute this if you input a and p-2 as exponents.

Practical Applications

This theorem isn’t just theory—it solves real problems.

• Cryptography: In RSA, exponents mod p use Fermat’s method for efficiency.
• Programming: Modular exponentiation in Python (pow(a,exp,p)) relies on it.
• Math Contests: Quick inverse calculations save time.

Step-by-Step Guide for Beginners

If you’re new, here’s a simple guide:

1. Understand Modulo: x mod n is the remainder. E.g., 10 mod 3 = 1.
2. Check p: Ensure it’s prime (e.g., 2, 3, 5, 7).
3. Input a: Any integer, positive or negative.
4. Run Calculator: See results and learn.

Tip: For large exponents, let the tool handle it—manual calc is slow.

Advanced Tips for Experts

• Binary Exponentiation: Compute 7^13 mod 11: 13=1101, split powers, multiply mod 11.
• Composite Moduli: Use Euler’s theorem (φ(n)) for non-primes.
• Pseudoprimes: Watch for false positives in primality tests.

FAQs Simplified

• Is 19^11 mod 11 = 8? 
• Yes, 19 mod 11=8, 8^11 mod 11=8 by theorem.
• Works for p=2? 
• Yes, for odd a, a^1 ≡ 1 mod 2.
• Large Exponents? 
• Use calc’s modpow function.

Why Trust This Calculator?

• Accuracy: Uses BigInt for large numbers.
• Error Checks: Flags non-prime p or invalid inputs.
• History-Based: Builds on Fermat’s 1640 insight, Euler’s 1736 proof.

Conclusion

The Fermat’s Little Theorem Calculator makes number theory accessible. Whether you’re verifying theorems, testing primes, or finding inverses, it guides you with clear outputs. Try it with your numbers and explore this classic result hands-on.