Congruences · Definition

Fermat's little theorem

elementary number theorycongruences

Before you start you need to know

Pierre de Fermat stated this result in the 17th century, and it plays a central role in number theory. It appears in primality tests and cryptographic algorithms.

Definition

Fermat's little theorem states that if \(p\) is a prime number and \(a\) is an integer not divisible by \(p\), then \(a^{p-1}\equiv 1 \pmod{p}\). It is a basic tool for simplifying modular powers.

\[a^{p-1}\equiv 1 \pmod{p}, \quad p\nmid a\]

If \(p\) is prime and \(p\nmid a\), the set \(\{a, 2a, \dots, (p-1)a\}\) is a complete set of nonzero residues modulo \(p\), so its product is congruent to \((p-1)!\). This gives \(a^{p-1}\equiv 1 \pmod{p}\), and since \((p-1)!\equiv -1\) by Wilson's theorem, the form \(a^p\equiv a \pmod{p}\) holds for every integer \(a\).

For example, to compute \(7^{222}\bmod 11\), since \(11\) is prime and \(11\nmid 7\), we have \(7^{10}\equiv 1 \pmod{11}\). As \(222=10\cdot 22+2\), we get \(7^{222}\equiv 7^2=49\equiv 5 \pmod{11}\).

A typical mistake is applying the theorem without checking that \(p\) is prime, or using it with \(a\) divisible by \(p\). For instance, with the non-prime \(p=9\), \(2^{8}=256\equiv 4 \pmod{9}\), not \(1\), so the conclusion fails.

Think about it

Why is \(2^{10}\equiv 1\pmod{11}\) enough to compute \(2^{100}\bmod 11\)?

Because \(100=10\cdot 10\), so \(2^{100}=(2^{10})^{10}\equiv 1^{10}=1\pmod{11}\).

Exercises 10

  1. By Fermat's little theorem, what is \(a^{p-1}\) congruent to modulo \(p\) when \(p\) is prime and \(p\nmid a\)?
  2. What is the value of \(3^{6}\bmod 7\)?
  3. If \(p\) is prime, what condition on \(a\) is needed to use \(a^{p-1}\equiv 1 \pmod{p}\)?
  4. What is the remainder of \(5^{12}\) when divided by \(13\)?
  5. If \(p=7\) and \(a=2\), what value does \(a^{p-1}\bmod p\) take?
  6. Compute \(2^{100}\bmod 11\).
  7. Find the remainder of \(3^{50}\) when divided by \(7\).
  8. What is the value of \(4^{30}\bmod 13\)?
  9. Compute \(6^{17}\bmod 17\).
  10. Find the remainder of \(2^{1000}+3^{1000}\) when divided by \(7\).

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 5
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2