Fermat's little theorem
Fermat’s Little Theorem
Introduction to Fermat’s Little Theorem
- Fermat’s Little Theorem is a fundamental result in number theory, named after the French mathematician Pierre de Fermat.
- The theorem has significant applications in Cryptography, especially in the field of Public Key Cryptography.
Statement of the 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) is congruent to 1 modulo p, usually expressed in mathematical notation as a^(p-1) ≡ 1 (mod p).
- Alternatively, it can be stated as: for any prime number p and any integer a, the number a^p is congruent to a modulo p, generally written as a^p ≡ a (mod p).
Applications in Cryptography
- Due to its properties, Fermat’s Little Theorem is used in the popular RSA algorithm which forms the backbone of secure communication over the internet.
- Understanding this theorem is a stepping stone to grasp advanced public-key cryptosystems.
Proof of the Theorem
- There are many proofs of Fermat’s Little Theorem, with varying levels of mathematical sophistication required. Understanding at least one proof is important for firmly grasping the concept.
- The most common and simple proof is by mathematical induction, which is expected to be understood at this level.
- Another commonly taught proof is based on group theory, specifically through the concept of cyclic groups.
Examples and Problems
- Evaluating numerical examples can help internalise the theorem: for example, taking p = 5 and a = 3, check that 3^(5-1) = 81 is indeed congruent to 1 modulo 5.
- It’s also beneficial to solve problems which require applying Fermat’s Little Theorem to compute large powers modulo a prime.
Extending the Theorem: Euler’s Totient Theorem
- Euler’s totient theorem can be viewed as a generalisation of Fermat’s Little Theorem, involving Euler’s totient function which counts the number of coprime numbers to a given number.
- This function and theorem introduce the concept of a totient, which has wide applications in number theory and cryptography.
Fermat’s Little Theorem and Primality Testing
- Fermat’s Little Theorem forms the basis of certain primality tests.
- The Fermat primality test and the Miller-Rabin primality test are probabilistic tests that quickly check if a number is prime, used widely in computational applications.
- Limitations of these tests and understanding when they may give incorrect results (known as Carmichael numbers) further deepens the comprehension of Fermat’s Little Theorem.