　$\varphi$ でEulerのtotient関数を表すものとする. 一般に $N\geq 2$ が非負整数 $l_2,l_3,l_5,l_{17},l_{257}$ を用いて
$$2^{l_{2}}\times 3^{l_{3}}\times 5^{l_{5}}\times 17^{l_{17}}\times 257^{l_{257}}$$
と表されるとする (このような $N$ を**良い整数**とよぶこととする).
また, 正の整数 $n$ と非負整数 $k$ に対し
$$a(n,0)=1,\quad a(n,k+1)=n^{a(n,k)}-1\quad(k=0,1,\dots)$$
と定める. さらに, 良い整数 $N$ と正の整数 $n$ に対し, ある正の整数 $K$ が存在して
$$a(n,K)\equiv a(n,K+1)\equiv\cdots \pmod N$$
となるとき, $a(n,K)$ を $N$ で割った余りを $f(N,n)$ と表すこととする. 

----

**主張1.**　任意の良い整数 $N$ と正の整数 $n$ に対し, $f(N,n)$ が定まる. 

**証明.**　中国剰余定理より, $N$ が素べき $p^l$ である場合に示せば十分である.
仮定から $p-1$ は $2$ のべきである.\
　$n=1$ のとき, 任意の $k\geq 1$ について $a(n,k)=0$ となるから, $f(N,n)=0$ と定まる.\
　$n=2$ のとき, 任意の $k$ について $a(n,k)=1$ となるから, $f(N,n)=1$ と定まる.\
　以下 $n\gt 2$ とする. このとき $a(n,0)\lt a(n,1)\lt \cdots$ となることに注意する.

- $n$ が $p$ の倍数のとき：\
　$k$ を十分大きな整数とするとき,
$$a(n,k)=n^{a(n,k-1)}-1\equiv -1\pmod N$$
となるから, $f(N,n)=N-1$ と定まる.
- $\gcd(p,n)=1$ かつ $n$ が奇数のとき：\
　$N,\varphi(N),\varphi^2(N),\dots$ はすべて $(2\text{のべき})\times(p\text{のべき})$ の形である.
また, ある $M$ が存在し $\varphi^M(N)=1$ となり,
現れる数がすべて $n$ と互いに素であることもわかる.\
　$k$ を任意の非負整数とするとき,
まず明らかに $a(n,k)$ は $\varphi^M(N)$ の倍数である.
すると $a(n,k+1)=n^{a(n,k)}-1$ はEulerの定理より $\varphi^{M-1}(N)$ の倍数である.
これを繰り返すことで, $a(n,k+M)$ が $N$ の倍数であることがわかる.
したがって $f(N,n)=0$ と定まる.
- $\gcd(p,n)=1$ かつ $n$ が偶数のとき：
$$a(n,k+2)-a(n,k+1)=n^{a(n,k+1)}-n^{a(n,k)}=n^{a(n,k)}(n^{a(n,k+1)-a(n,k)}-1)$$
であるから, $2^{a(n,p)}\geq p-1$ に注意すると, $a(n,p+2)-a(n,p+1)$ は $\varphi(p)=p-1$ の倍数である.\
　また, $a(n,p+k+1)-a(n,p+k)$が$\varphi(p^k)=(p-1)p^{k-1}$ の倍数であると仮定すると,
Eulerの定理より $n^{a(n,p+k+1)-a(n,p+k)}-1$ は $p^k$ の倍数であり、
$n^{a(n,p+k)}$ は $p-1$ の倍数であるから,
$$a(n,p+k+2)-a(n,p+k+1)$$
は $\varphi(p^{k+1})=(p-1)p^k$ の倍数である.\
　したがって, $k\geq l$ のとき $a(n,p+k+2)-a(n,p+k+1)$ は $N$の倍数であり, $f(N,n)$ は定まる.

----

　次に各 $N$ について $f(N,n)$ としてとりえる値の個数を考える.  まずは $N$ が素べき $p^l$ の場合を考察する.
主張1の証明に基づけば, $\gcd(p,n)=1$ かつ $n$ が偶数のとき, $f(N,n)$ がどのような値をとるか考察すればよい.\
　$n\equiv 1\pmod p$ のとき, LTEの補題より以下が成り立つから, 十分大きな $k$ について $a(n,k)$ は $p^l$ の倍数となる. 
$$v_p(a(n,k+1))=v_p(a(n,k))+v_p(n-1)$$
よって $f(p^l,n)=0$ である.  以下 $n\not\equiv 1\pmod p$ とする.

----

**主張2.**　$n_1,n_2$ を $4$ 以上の偶数であって, ともに $\bmod~p$ で $0,1$ と合同でないものとする. このとき,
$f(p^l,n_1)\not\equiv 0,-1\pmod{p}$ であり, $f(p^l,n_1)=f(p^l,n_2)$ ならば $n_1\equiv n_2\pmod{p^l}$ である. 

**証明.**　$l$ についての帰納法で示す. まず $l=1$ とする.  $n$ を $4$ 以上の偶数とするとき, 
十分大きな $k$ について
$$a(n,k)=n^{a(n,k-1)}-1\equiv -1\pmod{p-1}$$
となるから, 
$$a(n,k+1)=n^{a(n,k)}-1\equiv n^{-1}-1\pmod{p}$$
となる. よって $f(p,n)\equiv n^{-1}-1\pmod{p}$ より, $l=1$ の場合は成り立つ. \
　以下 $l=i$ の場合の成立を仮定し $l=i+1$ の場合を考える. 
$f(p^{i+1},n)\equiv f(p^i,n)\pmod{p^i}$ に注意すると, 
$f(p^{i+1},n)\not\equiv 0,-1\pmod p$ がわかる. 
また, 帰納法の仮定から, 
$f(p^{i+1},n_1)=f(p^{i+1},n_2)$ ならば
$$n_2=n_1+2sp^i$$
(ただし $s$ は整数) と表される. このとき, $k$ を十分大きな整数とすれば, 以下の各合同式
$$
\begin{aligned}
  a(n_1,k)&\equiv a(n_1+2sp^i,k) &\pmod{p^{i+1}}\\\\
  a(n_1,k)&\not\equiv 0 &\pmod{p}\\\\
  a(n_1,k)&\equiv a(n_1+2sp^i,k)(\equiv -1) &\pmod{p-1}
\end{aligned}
$$
が成り立つから, $D=a(n_1,k)$ とすると, Eulerの定理より
$$
\begin{aligned}
  && n_1^{a(n_1,k)}-1&\equiv (n_1+2sp^i)^{a(n_1+2sp^i,k)}-1 &\pmod{p^{i+1}}\\\\
  &\implies& n_1^D-1&\equiv (n_1+2sp^i)^D-1 &\pmod{p^{i+1}}\\\\
  &\implies& n_1^D-1&\equiv n_1^D+2Dn_1sp^i-1&\pmod{p^{i+1}}\\\\
  &\implies& 2Dn_1s&\equiv 0 &\pmod{p}\\\\
  &\implies& s&\equiv 0 &\pmod{p}
\end{aligned}
$$
以上より $l=i+1$ でも成立が示された.
----

　以上の議論をまとめると, $N=p^l$ において $f(N,n)$ は

- $p=2$ のとき $f(N,1)=0,f(N,2)=1$ で, 以降は $0,N-1$ を繰り返す.
- $p\geq 3$ のとき $f(N,1)=0,f(N,2)=1$ で, 以降は $p^{l-1}(p-2)+2$ 種類の値を周期 $2p^l$ で繰り返す.

したがって, 一般の $N$ (ただし $l_2\geq 2$, $l_3,l_5,l_7,l_{257}\geq 1$ )に対して, $f(N,n)$ のとり得る値の種類数は
$$1+2^4+\prod_{p=3,5,17,257}(p^{l_p-1}(p-2)+2)$$
であることが容易にわかる. 今回の $N$ について, この値は $\textbf{147487434}$ である.
公式解説
https://onlinemathcontest.com/contests/omc060/editorial/289
　$N=2^5\times 3^4\times 5^3\times 17^2\times 257$ について, 以下をみたす $0$ 以上 $N$ 未満の整数 $m$ の個数を求めてください.

- ある正の整数 $n$ と正の整数 $K$ が存在し, 整数列 $a_0,a_1,\dots$ を
  $$a_0=1,\quad a_{k+1}=n^{a_k}-1\quad(k=0,1,\dots)$$
  で定めると, $a_K\equiv a_{K+1}\equiv\cdots\equiv m\pmod N$ となる.