第3問

ある $n$ に対して奇素数 $p$ が $f(n)$ を割り切ると仮定する;このとき(境界を求めるべき残りの場合として $f\ne\mathrm{id}$ を仮定し)ステップ3を用いて $P(n,p)$ より $f(n)\mid p^n-f(p)^{f(n)}=p^n-1$ となり、特に $p\mid p^n-1$ となるが、$p\mid p^n$ なのでこれは偽である。したがって $f(n)$ を割り切る奇素数は存在せず、すなわちすべての $n$ で $f(n)$ は $2$ のべきである。ステップ1($f(n)\mid n^n$)と合わせると、$n$ が奇数なら $n^n$ も奇数なので、それを割り切る $2$ のべきは $1$ でなければならず、すべての奇数 $n$ で $f(n)=1$ となる。