# Number Theory: Fermat's little theorem

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