Problem 5

数

任意の正整数 a と n について、数列 a, a^a, a^{a^a}, a^{a^{a^a}}, \cdots は mod n でいつか定数になることを示せ

証明
あってると思うんだけど、ほんとにこんなんでええんかな…

問題の数列を b(i) と書くことにする

n についての帰納法で示す
n < k のときに成立すると仮定する

k = 1 のときは数列はつねに 0

k > 1 のときは\phi(k) < k だから、整数 N があって、
 c = b(N) = b(N+1) = b(N+2) = \cdots \,\,\, (\text{mod}\,\, \phi(k))
よってオイラーの定理から
 b(N+r+1) = a^{b(N+r)} = a^c \,\,\, (\text{mod}\,\, k)