# Number Theory: Fermat's little theorem

## Understanding Fermat’s Little Theorem

• Fermat’s Little Theorem is a fundamental theorem in number theory, named after Pierre de Fermat.
• It states that if p is a prime number and a is an integer not divisible by p, then a^(p-1) ≡ 1 (mod p).
• The notation “≡” means “congruent to”, and a ≡ b (mod p) means that a and b have the same remainder when divided by p.
• Fermat’s Little Theorem is often used as a primality test.

## Applying Fermat’s Little Theorem

• Fermat’s Little Theorem can be used to compute powers of integers modulo p.
• Let k = q(p-1) + r, where q and r are integers and 0 ≤ r < p-1. Then a^k ≡ a^r (mod p).
• This is particularly useful in cryptography, such as the RSA encryption process.

## Proving Fermat’s Little Theorem

• The theorem can be proved using mathematical induction, a method of mathematical proof.
• A key observation is that, for a prime p and any integer a not divisible by p, the integers a, 2a, …, (p-1)a are distinct and each is congruent to one of 1, 2, …, p-1 modulo p.
• This is because if ia ≡ ja (mod p) with 1 ≤ i < j ≤ p-1, then p must divide a(j-i), but this is impossible as neither a nor j-i is divisible by p.

## Using Fermat’s Little Theorem in Cryptography

• Many modern cryptosystems use Fermat’s Little Theorem, especially in the field of public key cryptography.
• For example, the RSA algorithm uses it in both the encryption and decryption steps.
• Fermat’s Little Theorem is a key pillar in the generation of public and private keys, secure transmission of data, and the decryption of the received data.

## Handling Composite Numbers

• Fermat’s Little Theorem doesn’t hold for composite numbers (non-primes). However, some composite numbers a do satisfy a^(n-1) ≡ 1 (mod n). These are known as Carmichael numbers, which are a type of pseudoprime.
• Detecting Carmichael numbers is therefore important when using Fermat’s Little Theorem as a probabilistic primality test, as they would pass the test but are not prime.