Fermat's Little Theorem & Euler's Theorem

Let $p$ be a prime. For every integer $a$ with $p\nmid a$, we have $a^{p-1}\equiv 1\pmod p$.

Let $p$ be a prime. For every integer $a$, we have $a^{p}\equiv a\pmod p$.

Let $p$ be prime and let $p\nmid a$. We first prove that for $i=1,2,\cdots,p-1$, the remainders $ia \bmod p$ are all distinct. Suppose otherwise. If there were $1\le i < j < p$ such that

But neither $(j-i)$ nor $a$ is a multiple of $p$, which is a contradiction.

In other words, these remainders form a permutation of $\{1,2,\cdots,p-1\}$. Hence,

This implies

In other words, the left-hand side is a multiple of $p$. However, none of $i=1,2,\cdots, p-1$ is a multiple of $p$, so the only possibility is $p\mid (a^{p-1}-1)$; that is, Fermat's little theorem holds.

The second formulation of Fermat's little theorem holds for every $a\in\mathbf N$, so we can use mathematical induction. The case of negative integers is easily reduced to that of nonnegative integers.

The base case is $0^p\equiv 0\pmod p$, which is obvious. Assume that the statement holds for $a\in\mathbf N$; we need to prove that it also holds for $a+1$. By the binomial theorem,

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

The second congruence uses the induction hypothesis. Thus, by mathematical induction, Fermat's little theorem holds.

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

As in the proof of Fermat's little theorem, take a sequence of numbers coprime to $m$ and operate on it. Consider the set

This is a reduced residue system modulo $m$. By the definition of the Euler totient function, $|R|=\varphi(m)$. As above, multiplying its elements by $a$ merely permutes the set:

Indeed, it is easy to verify that $\gcd(ar,m)=1$, and that distinct $r_1,r_2\in R$ give distinct values of $ar_1\bmod m$ and $ar_2\bmod m$. Hence,

Repeating the preceding argument and canceling $\prod_{r\in R}r$ gives $a^{\varphi(m)}\equiv 1\pmod m$.

For every positive integer $m$, integer $a$, and nonnegative integer $k$,

First, we show that there exists $k_0\in\mathbf N$ such that the integer $a$ is coprime to $m':=\dfrac{m}{\gcd(a^{k_0},m)}$. Let $\nu_p(n)$ denote, for an integer $n$, the exponent of the prime $p$ in its prime factorization. We may take

Every power of a prime common to $m$ and $a$ is then already contained in $a^{k_0}$, so $a$ is coprime to the remaining factor of $m$, namely $m'=\dfrac{m}{\gcd(a^{k_0},m)}$.

Now, for $k\ge k_0$, consider the congruence

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

Since $a$ is coprime to the modulus $m'$, Euler's theorem can be applied directly, giving

Multiplying back by $\gcd(a^{k_0},m)$ yields

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

The parameters obtained here are tighter than those in the statement of extended Euler's theorem, but are relatively difficult to compute. We can show that they can be relaxed to the parameters in that theorem. First, from the formula for the Euler totient function, since $m'\mid m$, we have $\varphi(m')\mid\varphi(m)$. In other words, $\varphi(m)$ is also a cycle length. Second, $k_0$ can be relaxed to $\varphi(m)$. For every $m\in\mathbf N_+$ and every $p\mid m$,

The inequality in the second line follows from the binomial expansion, retaining only the constant and linear terms. Therefore,

This completes the proof of the stated result.

The definition of $A\uparrow\uparrow B$ allows us to compute it recursively. To compute $(A\uparrow\uparrow B)\bmod M$, we only need to apply extended Euler's theorem and compute $(A\uparrow\uparrow(B-1))\bmod\varphi(M)$. Since $\varphi(\varphi(n)) \le n/2$ holds for all $n\ge 2$, the recursion always finishes within $O(\log M)$ steps. Because extended Euler's theorem is used, we must distinguish whether the current result is strictly smaller than the current modulus. This only requires one additional check when taking the remainder. Boundary cases also require attention.

#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;
  }
}