# 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.