令k代表2^((k-1))，1=2，是否在模素數意義下，對所有k大於等於某個數，k是常數？

01-02

也就是問2的2的2的2的....次方是不是會在次方足夠多次之後在模 p 意義下取到常數
問題背景是熟知的 bzoj 3884，對這道題廣為人知的看法看上去不是很 work

是的。

我們注意到當 $(k-1)^*>varphi(p)$ 時：

$k^*equiv 2^{(k-1)^*}equiv 2^{(k-1)^*modvarphi(p)+varphi(p)}pmod p$

而當 $(k-2)^*>varphi(varphi(p))$ 時：

$(k-1)^*equiv 2^{(k-2)^*}equiv 2^{(k-2)^*modvarphi(varphi(p))+varphi(varphi(p))}pmod{varphi(p)}$

……

當 $(k-i)^*>varphi^{(i)}(p)$ 時：

$(k-i)^*equiv 2^{(k-i-1)^*}equiv 2^{(k-i-1)^*modvarphi^{(i+1)}(p)+varphi^{(i+1)}(p)}pmod{varphi^{(i)}(p)}$

注意到這兩個性質：

所以一定存在一個 $i$ ，滿足 $varphi^{(i)}(p)=1$ ，同時對於這個 $i$ 一定存在一個 $k$ ，滿足對任意的 $j=0,1,cdots,i$ ，有 $(k-j)^*>varphi^{(j)}(p)$ 。

又因為

$(k-i)^*modvarphi^{(i)}(p)=(k-i+1)^*modvarphi^{(i)}(p)=0$

所以

$k^*=(k+1)^*$

這樣我們就可以證明

$k^*=(k+1)^*=(k+2)^*=cdots$

事實上這是LYDSY上的一道原題，見Problem 3884. -- 上帝與集合的正確用法

令k*代表2^((k-1)*)，1*=2，是否在模素數意義下，對所有k大於等於某個數，k*是常數？