第3問

$f\ne\mathrm{id}$ とし、$p$ を任意の奇素数とする;ステップ1より $f(p)$ は $p$ のべきで $f(p)=p^m$ とおける。$f(q)>1$ となる素数 $q$ は有限個しかないので、それらすべてより大きく $q\not\equiv1\pmod p$ を満たす素数 $q$ を選ぶ(単一の剰余類 $1\bmod p$ を避ける素数は無限に存在するのでこのような $q$ は存在する)と $f(q)=1$。すると $P(p,q)$ より $f(p)\mid q^p-f(q)^{f(p)}=q^p-1$。もし $m\ge1$ なら $p\mid f(p)\mid q^p-1$ となるが、フェルマーの小定理より $q^p\equiv q\pmod p$ なので $q$ の選び方から $q^p-1\equiv q-1\not\equiv0\pmod p$ となり矛盾する。よって $m=0$、すなわち $f(p)=1$。