Fermat's Little Theorem Calculator

Calculate modular arithmetic using Fermat's Little Theorem for prime number verification

Enter a base number and a prime to verify Fermat's Little Theorem: if p is prime and gcd(a,p)=1, then a^(p-1) ≡ 1 (mod p).

Must be a positive integer greater than 1

Must be a prime number greater than the base

Examples

Click on any example to load it into the calculator

Simple Prime Test

standardForm

Basic example with small prime number

a = 2

p = 7

Classic Example

standardForm

Traditional Fermat's Little Theorem demonstration

a = 3

p = 11

Alternative Form

alternativeForm

Using the alternative form of the theorem

a = 5

p = 13

Larger Prime

standardForm

Testing with a larger prime number

a = 4

p = 17

Other Titles
Understanding Fermat's Little Theorem Calculator: A Comprehensive Guide
Master the fundamental theorem in number theory that connects prime numbers, modular arithmetic, and cryptography applications

What is Fermat's Little Theorem? Mathematical Foundation and Significance

  • Fundamental theorem connecting prime numbers and modular arithmetic
  • Essential tool for primality testing and cryptographic applications
  • Bridge between abstract number theory and practical applications
Fermat's Little Theorem is one of the most elegant and fundamental results in number theory, discovered by Pierre de Fermat in 1640. This theorem establishes a crucial relationship between prime numbers and modular arithmetic that has profound implications for modern cryptography and computational number theory.
The theorem states: If p is a prime number and a is any integer not divisible by p (i.e., gcd(a,p) = 1), then a^(p-1) ≡ 1 (mod p). This means that when we raise a to the power of (p-1) and divide by p, the remainder is always 1.
An equivalent formulation is: For any integer a and prime p, we have a^p ≡ a (mod p). This alternative form applies to all integers a, regardless of whether they share common factors with p.
The theorem's power lies in its universality - it provides a consistent pattern that all prime numbers follow, making it invaluable for distinguishing primes from composite numbers and forming the foundation of many cryptographic algorithms.

Mathematical Demonstrations

  • 2^6 ≡ 1 (mod 7): 64 ≡ 1 (mod 7) since 64 = 9×7 + 1
  • 3^10 ≡ 1 (mod 11): 59049 ≡ 1 (mod 11) since 59049 = 5368×11 + 1
  • 5^12 ≡ 5 (mod 13): Both sides equal 5 when reduced modulo 13
  • Counter-example: 2^8 ≢ 1 (mod 9) because 9 is not prime

Step-by-Step Guide to Using Fermat's Little Theorem Calculator

  • Master the input requirements and parameter selection
  • Understand the different theorem forms and their applications
  • Interpret results and verify mathematical correctness
Our Fermat's Little Theorem calculator provides a comprehensive tool for exploring this fundamental theorem with automatic verification and detailed explanations of each step.
Input Requirements:
  • Base Number (a): Enter any positive integer greater than 1. This is the number that will be raised to various powers in the calculation.
  • Prime Number (p): Enter a prime number. The calculator automatically verifies that your input is indeed prime and provides feedback if it's not.
  • Theorem Form: Choose between the standard form a^(p-1) ≡ 1 (mod p) or the alternative form a^p ≡ a (mod p).
Automatic Verification Features:
  • Prime Verification: The calculator checks if the entered number is actually prime using efficient primality tests.
  • GCD Calculation: For the standard form, it verifies that gcd(a,p) = 1, ensuring the theorem's conditions are met.
  • Modular Arithmetic: Performs efficient modular exponentiation to handle large numbers without overflow.
Result Interpretation:
  • Calculation Display: Shows the complete calculation with intermediate steps for educational purposes.
  • Theorem Verification: Confirms whether the result satisfies Fermat's Little Theorem, helping identify potential input errors.

Calculator Usage Examples

  • Input: a=2, p=7 → Calculation: 2^6 mod 7 = 64 mod 7 = 1 ✓
  • Input: a=3, p=11 → Calculation: 3^10 mod 11 = 59049 mod 11 = 1 ✓
  • Input: a=4, p=9 → Error: 9 is not prime, theorem doesn't apply
  • Input: a=6, p=7 → Warning: gcd(6,7) = 1, so theorem applies normally

Real-World Applications of Fermat's Little Theorem in Technology and Cryptography

  • RSA Cryptography: The backbone of internet security
  • Primality Testing: Efficient algorithms for large numbers
  • Digital Signatures: Authentication and non-repudiation
  • Pseudorandom Number Generation: Cryptographic randomness
Fermat's Little Theorem serves as the mathematical foundation for numerous critical technologies that secure our digital world and enable modern computational number theory.
RSA Cryptosystem:
The RSA algorithm, used to secure everything from online banking to secure messaging, relies directly on Fermat's Little Theorem. The theorem ensures that the encryption and decryption processes are inverses of each other, enabling secure communication over insecure channels.
In RSA, the private key d is chosen such that ed ≡ 1 (mod φ(n)), where φ(n) is Euler's totient function. Fermat's Little Theorem guarantees that m^(ed) ≡ m (mod n) for the original message m, enabling perfect decryption.
Primality Testing:
Fermat's Little Theorem forms the basis of the Fermat primality test, one of the earliest probabilistic primality tests. If n is prime, then a^(n-1) ≡ 1 (mod n) for all a coprime to n.
While Carmichael numbers can fool simple Fermat tests, sophisticated variants like Miller-Rabin testing use Fermat's theorem as their foundation while addressing its limitations.
Digital Signatures and Authentication:
Digital signature algorithms like DSA and ECDSA use the mathematical properties ensured by Fermat's Little Theorem to provide authentication, integrity, and non-repudiation in digital communications.
Computational Applications:
  • Fast Modular Exponentiation: Computing a^b mod n efficiently using repeated squaring and Fermat's theorem
  • Cryptographic Hash Functions: Many hash functions incorporate principles from Fermat's theorem for security properties
  • Random Number Generation: Pseudorandom generators use modular arithmetic properties guaranteed by the theorem

Technology Applications

  • SSL/TLS certificates use RSA encryption based on Fermat's theorem for secure web browsing
  • Bitcoin and cryptocurrency signatures rely on elliptic curve variants of the theorem
  • Password hashing algorithms use modular arithmetic principles from the theorem
  • Online gaming anti-cheat systems use probabilistic primality tests for validation

Common Misconceptions and Correct Methods in Applying Fermat's Little Theorem

  • Understanding when the theorem applies and when it doesn't
  • Avoiding pitfalls with composite numbers and Carmichael numbers
  • Proper interpretation of modular arithmetic results
Despite its elegant simplicity, Fermat's Little Theorem is often misunderstood or misapplied. Understanding common misconceptions helps ensure correct usage in both theoretical and practical applications.
Misconception 1: The Theorem Works for All Numbers
Incorrect: Applying Fermat's Little Theorem to composite numbers will always give correct results.
Correct: The theorem only applies when p is prime. For composite numbers, the equation a^(n-1) ≡ 1 (mod n) may or may not hold, and when it does hold for composite n, these are called Carmichael numbers.
Misconception 2: Failed Fermat Test Means Compositeness
Incorrect: If a^(n-1) ≢ 1 (mod n), then n is definitely composite.
Correct: This is actually true! If the Fermat test fails for any a coprime to n, then n is certainly composite. The issue is with the converse - passing the test doesn't guarantee primality.
Misconception 3: GCD Condition is Optional
Incorrect: Fermat's Little Theorem works for any base a with any prime p.
Correct: For the standard form a^(p-1) ≡ 1 (mod p), we need gcd(a,p) = 1. If p divides a, then a ≡ 0 (mod p), and the theorem takes the form 0^(p-1) ≡ 0 (mod p), which is trivially true but not the interesting case.
Misconception 4: Larger Exponents Always Work
Incorrect: If a^(p-1) ≡ 1 (mod p), then a^k ≡ 1 (mod p) for any k > p-1.
Correct: This only works if k is a multiple of p-1. In general, a^k ≡ a^(k mod (p-1)) (mod p) by Fermat's Little Theorem, which is the basis for efficient modular exponentiation.
Best Practices:
  • Always verify that p is prime before applying the theorem
  • Check gcd(a,p) = 1 when using the standard form
  • Use multiple bases for probabilistic primality testing
  • Understand that passing Fermat tests is necessary but not sufficient for primality

Common Errors and Corrections

  • 561 = 3×11×17 is composite but 2^560 ≡ 1 (mod 561) - this is a Carmichael number
  • For p=7 and a=14, we have gcd(14,7)=7≠1, so standard form doesn't apply
  • 2^12 ≡ 2^0 = 1 (mod 13) since 12 ≡ 0 (mod 12) by Fermat's theorem
  • Testing n=25 with a=2: 2^24 ≡ 16 ≢ 1 (mod 25), so 25 is composite

Mathematical Derivation and Advanced Examples of Fermat's Little Theorem

  • Proof techniques: combinatorial, group theory, and induction approaches
  • Connection to Euler's theorem and generalizations
  • Advanced applications in computational number theory
Understanding the mathematical foundations of Fermat's Little Theorem provides deeper insight into its applications and connects it to broader areas of mathematics including group theory, combinatorics, and abstract algebra.
Combinatorial Proof:
Consider the number of ways to arrange a objects of p different colors in a circle, where each color appears at least once. By direct counting, this equals a^p - a arrangements (total arrangements minus those using fewer than p colors).
However, we can also count by considering rotational symmetry. Since p is prime, each arrangement has exactly p rotational variants unless all objects are the same color. Since there are a such monochromatic arrangements, the remaining a^p - a arrangements form groups of size p.
Therefore, p divides a^p - a, which means a^p ≡ a (mod p), proving Fermat's Little Theorem through pure combinatorial reasoning.
Group Theory Perspective:
In the multiplicative group (Z/pZ)* of integers modulo p (excluding 0), every element a satisfies a^(p-1) = 1 since the group has order p-1. This is a direct application of Lagrange's theorem from group theory.
This perspective shows that Fermat's Little Theorem is actually a special case of Lagrange's theorem, connecting elementary number theory to abstract algebra and revealing the deep structural reasons why the theorem holds.
Connection to Euler's Theorem:
Fermat's Little Theorem is a special case of Euler's theorem: for any integer a and positive integer n with gcd(a,n) = 1, we have a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function.
When n = p is prime, φ(p) = p-1, so Euler's theorem reduces to Fermat's Little Theorem. This connection shows how Fermat's insight generalizes to composite moduli.
Advanced Computational Applications:
  • Miller-Rabin Primality Testing: Uses Fermat's theorem with additional structure to detect Carmichael numbers
  • Fast Modular Exponentiation: Computes a^b mod n efficiently using a^(b mod (p-1)) when n = p is prime
  • Cryptographic Key Generation: RSA key generation relies on Fermat's theorem to ensure encryption/decryption consistency
  • Discrete Logarithm Problems: The hardness of these problems, crucial for cryptography, is partly based on Fermat's theorem structure

Advanced Mathematical Examples

  • Proof verification: For p=5, check all a ∈ {1,2,3,4}: 1^4≡1, 2^4≡1, 3^4≡1, 4^4≡1 (mod 5)
  • Euler generalization: 3^φ(10) = 3^4 ≡ 1 (mod 10) since gcd(3,10)=1 and φ(10)=4
  • Fast computation: 2^1000 mod 7 = 2^(1000 mod 6) = 2^4 = 16 ≡ 2 (mod 7)
  • Miller-Rabin test: For n=341=11×31, check if 2^340 has specific square root structure