Chapter

Fermat and Euler

Fermat's Little Theorem, Euler's totient function, Euler's theorem, modular inverses, and large power computations.

Back to Course Practice Ladders
Theory Examples Practice Ladders

Theory

1. Fermat's Little Theorem

If \(p\) is prime and \(p\nmid a\), then

\[ a^{p-1}\equiv1\pmod p. \]

Equivalently, for every integer \(a\),

\[ a^p\equiv a\pmod p. \]

This theorem is a powerful way to reduce large powers modulo a prime.

2. Modular Inverses

If \(\gcd(a,m)=1\), then \(a\) has an inverse modulo \(m\). That means there is an integer \(b\) such that

\[ ab\equiv1\pmod m. \]

Fermat's theorem gives a useful inverse modulo a prime:

\[ a^{-1}\equiv a^{p-2}\pmod p. \]

3. Euler's Totient Function

Euler's totient function \(\varphi(n)\) counts the positive integers from \(1\) to \(n\) that are relatively prime to \(n\). For example,

\[ \varphi(10)=4, \]

because \(1,3,7,9\) are relatively prime to \(10\).

If

\[ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}, \]

then

\[ \varphi(n)=n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots\left(1-\frac1{p_k}\right). \]

4. Euler's Theorem

If \(\gcd(a,n)=1\), then

\[ a^{\varphi(n)}\equiv1\pmod n. \]

Fermat's Little Theorem is the special case when \(n\) is prime.

5. Strategy for Large Powers

To compute \(a^k\pmod n\):

  1. Check whether \(\gcd(a,n)=1\).
  2. If yes, reduce the exponent modulo \(\varphi(n)\), or use a shorter cycle.
  3. If not, use direct factorisation, prime powers, or another modulus.

Examples

Example 1. Fermat Modulo Five

This is the cleanest first FLT computation.

Problem. Find \(3^{2026}\pmod5\).
Solution. By Fermat's theorem, \(3^4\equiv1\pmod5\). Since \(2026\equiv2\pmod4\), \(3^{2026}\equiv3^2=9\equiv4\pmod5\).

Example 2. Fast Power Modulo Seven

Short cycles may be better than a theorem.

Problem. Find \(2^{100}\pmod7\).
Solution. Since \(2^3=8\equiv1\pmod7\), reduce the exponent modulo \(3\). Since \(100\equiv1\pmod3\), \(2^{100}\equiv2\pmod7\).

Example 3. Totient by Listing

Listing before formula keeps the function meaningful.

Problem. Find \(\varphi(12)\) by listing the positive integers from \(1\) to \(12\) that are coprime to \(12\).
Solution. The numbers are \(1,5,7,11\). Hence \(\varphi(12)=4\).

Example 4. Totient Formula

Require prime factorisation before applying the formula.

Problem. Find \(\varphi(45)\).
Solution. \(\varphi(45)=45\left(1-\frac13\right)\left(1-\frac15\right)=45\cdot\frac23\cdot\frac45=24\).

Example 5. Euler Modulo Ten

Connect Euler theorem to familiar last-digit work.

Problem. Find the last digit of \(7^{100}\).
Solution. Euler's theorem gives \(7^4\equiv1\pmod{10}\). Since \(100\equiv0\pmod4\), \(7^{100}\equiv1\pmod{10}\). The last digit is \(1\).

Example 6. Inverse Modulo Eleven

Do this by inspection before using Fermat's formula.

Problem. Find the inverse of \(3\) modulo \(11\).
Solution. \(3\cdot4=12\equiv1\pmod{11}\), so the inverse is \(4\).

Example 7. Fermat Inverse

This is conceptually important for solving congruences.

Problem. Use Fermat's Little Theorem to explain why \(a^{p-2}\) is an inverse of \(a\pmod p\) when \(p\) is prime and \(p\nmid a\).
Solution. By Fermat's theorem, \(a^{p-1}\equiv1\pmod p\). But \(a\cdot a^{p-2}=a^{p-1}\), so \(a\cdot a^{p-2}\equiv1\pmod p\). Therefore \(a^{p-2}\) is an inverse of \(a\pmod p\).

Example 8. Euler Power

Again, short cycles are often more efficient than full Euler theorem.

Problem. Find \(5^{123}\pmod8\).
Solution. Since \(5^2=25\equiv1\pmod8\), odd powers of \(5\) are congruent to \(5\pmod8\). Hence \(5^{123}\equiv5\pmod8\).

Problems

Problems

No published problems are available yet.

Ladders

No published ladders were found.
Previous Chapter
Next Chapter