Fermat's Little Theorem Calculator
Compute aᵖ⁻¹ mod p, which is 1 when p is prime and a is not a multiple of p.
Fermat's Little Theorem is a cornerstone of number theory and underpins primality testing and RSA.
How the Math Works
Fermat's Little Theorem states that for a prime number p and an integer a not divisible by p, the equation a^(p-1) ≡ 1 (mod p) holds true. This calculator leverages this principle to compute a^(p-1) mod p, effectively verifying primality by checking if the result equals 1. When p is prime and a is not a multiple of p, the remainder after division by p will always be 1, making this a quick computational test for prime numbers in many applications.
Practical Applications
This theorem is widely used in cryptography and computer science for primality testing, especially in algorithms requiring large prime numbers. For example, to check if 7 is prime, input a=3 and p=7 into the calculator: 3^6 mod 7 equals 1, confirming 7 is prime. It also aids in generating cryptographic keys where prime verification is essential, and in solving modular arithmetic problems in competitive programming or mathematical research involving number theory.
Day-to-Day Use
In daily life, Fermat's Little Theorem underpins the security of online transactions, such as banking or shopping, by helping generate encryption keys that rely on large primes. It also simplifies calculations in educational settings, allowing students to explore number theory concepts interactively. Additionally, it supports error-checking in digital communications and coding challenges, ensuring reliable data transmission and problem-solving in fields like software development or algorithm design.
Worked example
3⁶ mod 7 = 729 mod 7 = 1, confirming 7 is prime.
FAQ
Does result 1 prove p is prime?
Not always — some composites (Carmichael numbers) also pass; it's a strong hint, not a proof.