Skip to content

Fermat's Little Theorem & Euler's Theorem

This article discusses Fermat's little theorem, Euler's theorem, and their extensions. These theorems address the computation of powers with arbitrarily large exponents under arbitrary moduli.

Fermat's Little Theorem

Fermat's little theorem is one of the most fundamental theorems in number theory. It also serves as the theoretical basis for Fermat primality test.

Fermat's Little Theorem

Let \(p\) be a prime. For any integer \(a\) such that \(p\nmid a\), we have \(a^{p-1}\equiv 1\pmod p\).

Theorem

Let \(p\) be a prime. For any integer \(a\), we have \(a^{p}\equiv a\pmod p\).

These two congruences are equivalent when \(p\nmid a\); when \(p\mid a\), \(a^p\equiv 0\equiv a\pmod p\) trivially holds. Therefore, these two statements are equivalent. Both statements are often referred to as Fermat's little theorem.

Proof 1

Let \(p\) be a prime, and \(p\nmid a\). First, prove that for \(i=1,2,\cdots,p-1\), the remainders \(ia \bmod p\) are all distinct. Assume for contradiction that there exist \(1\le i < j < p\) such that

\[ ia \bmod p = ja \bmod p. \iff (j-i)a\equiv 0.\pmod p \]

However, neither \((j-i)\) nor \(a\) is a multiple of \(p\), which is clearly a contradiction.

In other words, these remainders form a permutation of \(\{1,2,\cdots,p-1\}\). Therefore, we have

\[ \prod_{i=1}^{p-1}i = \prod_{i=1}^{p-1}(ia\bmod p) \equiv \prod_{i=1}^{p-1}ia = a^{p-1}\prod_{i=1}^{p-1}i.\pmod p \]

This implies

\[ (a^{p-1}-1)\prod_{i=1}^{p-1}i \equiv 0. \pmod{p} \]

That is, the left-hand side is a multiple of \(p\), but \(i=1,2,\cdots, p-1\) are not multiples of \(p\). Hence, we must have \(p\mid (a^{p-1}-1)\), i.e., Fermat's little theorem holds.

Proof 2

Note that the second formulation of Fermat's little theorem holds for all \(a\in\mathbf N\). Therefore, we can use mathematical induction. The case for negative integers can be easily reduced to non-negative integers.

The base case is \(0^p\equiv 0\pmod p\), which obviously holds. Assume it holds for \(a\in\mathbf N\). We need to prove it holds for \(a+1\). By the binomial theorem,

\[ (a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{p-1}a+1. \]

Except for the first and last terms, the binomial coefficient \(\dbinom{p}{k} = \dfrac{p!}{k!(p-k)!}\) has \(p\) dividing the numerator but not the denominator. Therefore, these coefficients are multiples of \(p\) for \(k\neq 0,p\). Thus,

\[ (a+1)^p \equiv a^p + 1\equiv a + 1. \pmod{p} \]

where the second step uses the induction hypothesis. Hence, by mathematical induction, Fermat's little theorem holds.

The converse of Fermat's little theorem is not true. Even if \(a^{n-1}\equiv 1\pmod n\) for all \(a\) coprime to \(n\), \(n\) may not be prime. Related discussions can be found in the section on Fermat primality test.

Euler's Theorem

Euler's theorem generalizes Fermat's little theorem to general moduli, but still requires the base and modulus to be coprime.

Euler's Theorem

For integers \(m>0\) and \(a\) with \(\gcd(a,m)=1\), we have \(a^{\varphi(m)}\equiv 1\pmod{m}\), where \(\varphi(\cdot)\) is the Euler totient function.

Proof

Similar to Proof 1 of Fermat's little theorem, we take a sequence coprime to \(m\) and perform operations. Consider the set

\[ R = \{r\in\mathbf N : 0 < r < m,~\gcd(r,m)=1\}. \]

This is the reduced residue system modulo \(m\). By definition of the Euler totient function, \(|R|=\varphi(m)\). As above, multiplying them by \(a\) corresponds to permuting the set:

\[ R = \{ar\bmod m: r\in R\}. \]

This is because it is easy to verify \(\gcd(ar,m)=1\) and different \(r_1,r_2\in R\) yield different \(ar_1\bmod m\) and \(ar_2\bmod m\). Therefore,

\[ \prod_{r\in R}r \equiv \prod_{r\in R}ar = a^{\varphi(m)}\prod_{r\in R}r. \pmod{m} \]

Repeating the previous argument, canceling \(\prod_{r\in R}r\) yields \(a^{\varphi(m)}\equiv 1\pmod m\).

For a prime \(p\), \(\varphi(p)=p-1\), so Fermat's little theorem is a special case of Euler's theorem. Additionally, the exponent \(\varphi(m)\) in Euler's theorem is not necessarily the smallest exponent that makes the congruence hold in general. It can be improved to \(\lambda(m)\), where \(\lambda(\cdot)\) is the Carmichael function. For algebraic background on related results, refer to the section on multiplicative group of integers modulo n.

Extended Euler's Theorem

The extended Euler's theorem1 further generalizes the result to cases where the base and modulus are not coprime. Consequently, it completely solves the problem of computing powers with arbitrary bases under arbitrary moduli, reducing them to cases where the exponent is less than \(2\varphi(m)\). This allows computation via fast exponentiation in \(O(\log\varphi(m))\) time.

Extended Euler's Theorem

For any positive integer \(m\), integer \(a\), and non-negative integer \(k\), we have

\[ a^k \equiv \begin{cases} a^{k \bmod \varphi(m)}, &\gcd(a,m) = 1, \\ a^k, &\gcd(a,m)\ne 1, k < \varphi(m), \\ a^{(k \bmod \varphi(m)) + \varphi(m)}, &\gcd(a,m)\ne 1, k \ge \varphi(m). \end{cases} \pmod m \]

The second case states that if \(k < \varphi(m)\), there is no need to reduce the exponent further; simply apply fast exponentiation. The key difference between the third and first cases is whether an extra term \(\varphi(m)\) needs to be added after reducing the exponent modulo \(\varphi(m)\). Of course, merging the first case into the second or third cases is also correct.

Intuitive Understanding

Before giving a rigorous proof, we can first intuitively understand the theorem's meaning.

fermat1

Consider how the remainder \(a^k\bmod m\) changes as \(b\) increases. Since the remainder must lie in the interval \([0,m)\) and there are infinitely many \(k\), view \(a^k\bmod m \mapsto a^{k+1}\bmod m\) as directed edges between these remainder nodes. Then, cycles as shown in the figure must form.

The extended Euler's theorem indicates that these cycles may be pure cycles (first case) or mixed cycles (second and third cases). In pure cycles, no node has two predecessors, whereas mixed cycles exhibit such nodes. Therefore, for the general case, it suffices to determine the cycle length and the length before entering the cycle, then use this property to reduce the exponent.

Rigorous Proof

This section provides a rigorous proof of the extended Euler's theorem.

Proof

First, note that there exists \(k_0\in\mathbf N\) such that integer \(a\) and \(m':=\dfrac{m}{\gcd(a^{k_0},m)}\) are coprime. To see this, let \(\nu_p(n)\) denote the exponent of prime \(p\) in the prime factorization of integer \(n\). Then, we can take

\[ k_0 = \max\left\{\left\lceil\dfrac{\nu_p(m)}{\nu_p(a)}\right\rceil : \nu_p(a)>0\right\}. \]

Because all common prime factors between \(m\) and \(a\) are already included in \(a^{k_0}\), \(a\) becomes coprime with the remaining factor \(m'=\dfrac{m}{\gcd(a^{k_0},m)}\) of \(m\).

Next, for \(k\ge k_0\), consider the congruence

\[ b\equiv a^k. \pmod m \]

Since \(\gcd(a^{k_0},m)=\gcd(a^k,m)\mid b\), dividing both sides (including the modulus) by \(\gcd(a^{k_0},m)\) yields

\[ \dfrac{b}{\gcd(a^{k_0},m)} = \dfrac{a^{k_0}}{\gcd(a^{k_0},m)}\cdot a^{k-k_0}. \pmod{m'} \]

Now, because \(a\) is coprime with modulus \(m'\), we can directly apply Euler's theorem to obtain

\[ \dfrac{b}{\gcd(a^{k_0},m)} \equiv \dfrac{a^{k_0}}{\gcd(a^{k_0},m)}\cdot a^{(k-k_0)\bmod\varphi(m')}. \pmod{m'} \]

Therefore, multiplying back the factor \(\gcd(a^{k_0},m)\) gives

\[ b \equiv a^{k_0}\cdot a^{(k-k_0)\bmod\varphi(m')} = a^{k_0 + (k-k_0)\bmod\varphi(m')}. \pmod{m} \]

This yields the form of the extended Euler's theorem. The expression shows that the cycle length is \(\varphi(m')\), and the length before entering the cycle is \(k_0\).

The parameters obtained here are tighter than those in the extended Euler's theorem, but they are relatively difficult to compute. It can be shown that these parameters can be relaxed to those in the extended Euler's theorem. First, using the expression for Euler's totient function, since \(m'\mid m\), we have \(\varphi(m')\mid\varphi(m)\). That is, \(\varphi(m)\) is also a cycle length. Second, \(k_0\) can also be relaxed to \(\varphi(m)\). This is because for all \(m\in\mathbf N_+\) and any \(p\mid m\),

\[ \begin{aligned} \varphi(m) &\ge \varphi(p^{\nu_p(m)}) = (p-1)p^{\nu_p(m)-1} \ge p^{\nu_p(m)-1} \\ &= (1+(p-1))^{\nu_p(m)-1} \ge 1 + (p-1)(\nu_p(m)-1) \\ &\ge 1 + (\nu_p(m)-1) = \nu_p(m). \end{aligned} \]

where the inequality in the second line uses binomial expansion, keeping only the constant and linear terms. Therefore,

\[ k_0 \le \max\{\nu_p(m):p\in\mathbf P\}\le \varphi(m). \]

This completes the proof.

Example

This section demonstrates a classic application of the extended Euler's theorem through an example—computing power towers under arbitrary moduli. A power tower is an expression of the form \(A\uparrow(B\uparrow(C\uparrow(D\uparrow\cdots)))\), where \(\uparrow\) is Knuth's up-arrow notation, and \(A,B,C,D,\cdots\) are non-negative integers.

Library Checker - Tetration Mod

There are \(T\) test cases. In each test, given \(A,B,M\), compute \((A\uparrow\uparrow B)\bmod M\). Here, \(A\uparrow\uparrow B\) denotes a power tower of \(B\) copies of \(A\). Formally, define

\[ A \uparrow\uparrow B = \begin{cases} 1 , & B = 0,\\ A\uparrow(A\uparrow\uparrow(B-1)), & B > 0. \end{cases} \]

Define \(0^0=1\).

Solution

Use the definition of \(A\uparrow\uparrow B\) and compute recursively. To compute \((A\uparrow\uparrow B)\bmod M\), simply apply the extended Euler's theorem to compute \((A\uparrow\uparrow(B-1))\bmod\varphi(M)\). Since \(\varphi(\varphi(n)) \le n/2\) holds for all \(n\ge 2\), the recursion terminates within \(O(\log M)\) steps. Because the extended Euler's theorem is applied, we need to distinguish whether the current computation result is strictly less than the current modulus. This can be done by an extra check during modulo operation. Additionally, careful handling of edge cases is required.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>

// Calculate Euler's totient for n.
int phi(int n) {
  int res = n;
  for (int i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      res = res / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  }
  if (n > 1) res = res / n * (n - 1);
  return res;
}

// Find remainder as in the exponent of extended Euler theorem.
int mod(long long v, int m) { return v >= m ? v % m + m : v; }

// Modular power.
int pow(int a, int b, int m) {
  long long res = 1, po = a;
  for (; b; b >>= 1) {
    if (b & 1) res = mod(res * po, m);
    po = mod(po * po, m);
  }
  return res;
}

// Modular tetration.
int tetra(int a, int b, int m) {
  if (a == 0) return !(b & 1);
  if (b == 0 || m == 1) return 1;
  if (b == 1) return mod(a, m);
  return pow(a, tetra(a, b - 1, phi(m)), m);
}

int main() {
  int t;
  std::cin >> t;
  for (; t; --t) {
    int a, b, m;
    std::cin >> a >> b >> m;
    std::cout << (tetra(a, b, m) % m) << std::endl;
  }
}

Exercises

References and Notes

  1. This name is primarily used in the competitive programming community and is not a universal name for this result. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用