扩展中国剩余定理 (exCRT)

扩展欧拉定理揭示了对于任意模数 $n$，有 $$a^b\bmod n=\begin{cases} a^b,&b<\varphi(n)\\ a^{b\bmod \varphi(n)+\varphi(n)},&\text{otherwise} \end{cases}.$$

我们又知道若分解质因数 $x=\sum p_i^{c_i}$，则 $\varphi(x)=x\prod (p_i-1)/p_i$。则若 $x>1$，若 $2\mid x$，$\varphi(x)\leq x/2$；否则，$2\mid\varphi(x)$。记 $\varphi^{(k)}(x)=\underbrace{\varphi(\varphi(\cdots\varphi(}_{k\text{ layers}}x)\cdots))$，则 $\newcommand\bigO{\operatorname{O}}\bigO(\log n)$ 级别的 $k$ 就能使其收敛到 $1$。

因此对于 $\mathbb{Z}/n\mathbb{Z}$ 上的超-4运算 $a_1^{a_2^{a_3^{⋰}}}$，结合扩展欧拉定理得到，在指数塔的 $\bigO(\log n)$ 层就将得到 $\bmod\varphi(1)+\varphi(1)\equiv 1$ 的指数。从而它是收敛的。 （更多…）