Fermat's Little Theorem & Primality Checker

Check primality and Fermat's condition for given values

Check Primality and Fermat's Condition

Enter values for p and a to test if:

  • p is prime (using the AKS primality test).
  • If p is prime and not divisible by a, then Fermat's Little Theorem states: a^(p-1) ≡ 1 (mod p).

About Fermat's Little Theorem

Fermat's Little Theorem states that if p is a prime number and a is any integer not divisible by p, then:

a^(p-1) ≡ 1 (mod p)

Key Points:

  • Primality Test: While Fermat's Little Theorem can be used as a primality test, it's not foolproof. Some composite numbers (called Fermat pseudoprimes) can satisfy the theorem.
  • AKS Primality Test: A deterministic polynomial-time algorithm for primality testing, though our implementation is simplified.
  • Modular Arithmetic: The theorem uses modular arithmetic, which is essential in number theory and cryptography.

Common Examples:

  • p = 7, a = 3: 3^6 = 729 ≡ 1 (mod 7) ✓
  • p = 11, a = 2: 2^10 = 1024 ≡ 1 (mod 11) ✓
  • p = 15, a = 2: 2^14 = 16384 ≡ 4 (mod 15) ✗ (15 is composite)