第3問

前のステップより $f(q)\mid q^q$ なので、$f(q)>1$ なら $f(q)$ は $q$ のべきである。このとき $P(q,n)$ より $q\mid f(q)\mid n^q-f(n)^{f(q)}$;フェルマーの小定理により $n^q\equiv n\pmod q$ であり、フェルマーを繰り返すことで $f(n)^{f(q)}\equiv f(n)\pmod q$($f(q)$ が $q$ のべきなので)となるので、$q\mid n-f(n)$ がすべての $n$ で成り立つ。これが無限に多くの素数 $q$ で成り立つなら、$n-f(n)$ はすべての $n$ に対していくらでも大きな素数で割り切れることになり、すべての $n$ で $f(n)=n$ が強制される、すなわち $f=\mathrm{id}$ となる。したがって $f=\mathrm{id}$ でない限り、$f(q)>1$ を満たす素数 $q$ は有限個しかない。