扩展欧拉定理

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

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

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

More
  • 2023年11月30日