DataTerminology.comNEW
A theorem stating properties of exponents modulo a prime, used in cryptography.
DESCRIPTION
Fermat’s Little Theorem states that for prime p and integer a, a^p ≡ a (mod p). If a is not divisible by p, then a^(p−1) ≡ 1 (mod p). It underlies modular inverses and primality testing. Cryptosystems like RSA rely on related number-theoretic properties. Extensions and caveats include pseudoprimes and Carmichael numbers. The theorem is fundamental in computational number theory and algorithm design.
ALTERNATIVE DEFINITIONS
Wikipedia
Fermat’s little theorem states that if p is a prime number, then for any integer a, a^p ≡ a (mod p).
Provides the core statement used in modular arithmetic and cryptography.
Wolfram MathWorld
Fermat’s little theorem asserts that for prime p and integer a, a^p ≡ a (mod p); if p ∤ a, then a^(p−1) ≡ 1 (mod p).
Includes both forms and divisibility condition explicitly.
Encyclopaedia Britannica
The theorem states that if p is prime and a is an integer, then a^p minus a is divisible by p.
Expresses theorem equivalently via divisibility rather than congruence.
Khan Academy
Fermat’s little theorem says that if p is prime and a is any integer not divisible by p, then a^(p−1) ≡ 1 (mod p).
Focuses on the reduced form used in cryptographic applications.
RELATED TERMS
Modular Arithmetic Prime Numbers RSA Multiplicative Inverse Number Theory Group Theory Data Encryption Pseudoprime Carmichael Number
COMPETING TERMS
KNOWLEDGE AREAS
TARGET AUDIENCE
Software Developer Cybersecurity Engineer Security Architect Chief Information Security Officer Data Scientist
EXTERNAL SOURCES
- Wikipedia - Fermat’s little theorem
- Wikipedia - Canonical theorem overview
- Wolfram MathWorld - Reference and proofs
- Khan Academy - Educational explanation
TOP QUESTIONS
What does Fermat’s Little Theorem state?
For prime p and any integer a, a^p ≡ a (mod p), and if p doesn’t divide a, then a^(p−1) ≡ 1 (mod p).
Category: Overview
Why is Fermat’s Little Theorem important in cryptography?
It underlies modular arithmetic operations, supporting modular inverses, primality tests, and properties used by RSA and related schemes.
Category: Relevancy
How does it relate to Euler’s Theorem?
Euler’s Theorem generalizes it to any modulus n coprime with a, replacing p−1 with φ(n).
Category: Alternatives
What is a common misunderstanding?
Assuming it proves primality; pseudoprimes can satisfy the congruence for some bases, requiring stronger tests.
Category: Misunderstanding
How is it used to compute modular inverses?
For prime p, a^(p−2) serves as the inverse of a modulo p when p does not divide a.
Category: Example
What are Carmichael numbers?
Composite numbers that satisfy Fermat-like congruences for all coprime bases, complicating primality testing.
Category: Risk
How to learn the theorem quickly?
Study modular arithmetic basics, then proofs via group theory or induction, and practice with computing inverses.
Category: Requirements
Is Fermat’s Little Theorem outdated?
No, it remains foundational in number theory and practical cryptography.
Category: Relevancy
What is the biggest difference of opinion?
Whether to teach it via elementary number theory or abstract algebra; both yield insights for different audiences.
Category: Opinion