This site is supported by donations to The OEIS Foundation.

# Fermat's little theorem

From OeisWiki

**Fermat’s little theorem** has big consequences in number theory and its applications, such as data encryption.^{[1]} It is called “little” only in deference to Fermat’s last theorem, and some authors in fact call it just **Fermat’s theorem**.^{[2]}

Theorem.(Pierre de Fermat)

Given a prime numberand an integer

pcoprime to

b,

p.

bp− 1 ≡ 1 (modp)Proof.Consider thenumbers

p− 1. Those are all different and nonzero

b, 2b, 3b, ..., (p− 1)b, since

(mod p)is prime and

pis coprime to

b. Indeed, if

p, then

ub≡vb(modp), since we can “cancel the

u≡v(modp)” (

bbeing coprime to

b). So we have

pnumbers, all different, and none of them is 0

p− 1. So they must be congruent to

(mod p)in some order. Multiplying them together, we get

1, 2, 3, ..., p− 1. So their product is congruent to

P= (p− 1)!bp− 1. We now have two expressions for this product, so we can equate them:

( p− 1)! (modp)Now

( p− 1)!bp− 1 ≡ (p− 1)! (modp).is coprime to

( p− 1)!, so we can again cancel, to give

p. □

bp− 1 ≡ 1 (modp)

For example, 10 12 is 1 more than 999999999999, which is divisible by 13 (as it is 76923076923 × 13).

b ϕ (n) ≡ 1 (mod n) |

gcd (b, n) = 1 |

^{[3]}since

ϕ ( p) = p − 1 |

gcd (b, p) = 1 |

b |

p |

The theorem is best demonstrated with small odd primes, such as 3 and 5. In the case of

p = 3 |

p = 2 |

## Contents

## Fermat pseudoprimes

However, the theorem can’t be used as a proof of primality forn |

b |

n |

n |

b n − 1 ≡ 1 (mod n) |

b |

n |

For example, for the composite number 341 = 11 × 31, we have

- 2 340 = 2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271607115776,

which leaves a remainder of 1 when divided by 341. However,

- 3 340 = 1664280806589814803858571371708626691451909331385734291010900950997276297957762658553727546535190828834204613885667545045874010453464713005017905547836267732294801,

b |

^{[4]}

In the case of 341, we can see that among small bases, remainders other than 1 are given often enough, e.g.

n 340 |

- {1, 1, 56, 1, 67, 56, 56, 1, 67, 67, 253, 56, 67, 56, 1, 1, 56, 67, 56, 67, 67, 253, 1, 56, 56, 67, 1, 56, 1, 1, 155, 1, 187, 56, 1, 67, 56, 56, 1, 67, 67, 67, 56, 253, 56, 1, 1, 56, 67, 56, 67, 67, 67, 1, 242, ...}

### Absolute Fermat pseudoprimes

So, what about testing for all basesb |

n |

b |

n |

## See also

- Chinese hypothesis
- A000790: Primary pretenders: least composite

such that*c*

.*n**c*≡*n*(mod*c*)

## Notes

- ↑ Schroeder (2009), p. 139.
- ↑ Such as Manfred R. Schroeder.
- ↑ Ethan D. Bolker,
*Elementary Number Theory: An Algebraic Approach*. Mineola, New York: Dover Publications (1969, reprinted 2007) p. 16, Theorems 9.6 and 9.7. - ↑ R. Crandall and C. Pomerance.
*Prime Numbers: A Computational Perspective*New York: Springer-Verlag (2001): p. 121.

## References

- Manfred R. Schroeder,
*Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing and Self-Similarity*, 5th Ed. Springer (2009).

## External links

- Joe Crump, 2
*n*mod*n*=*c*(in German).^{[dead link]}