代表選考合宿 2021
問題 10

頂点 $1,2,\dots,p$ と，$i=1,2,\dots,p$ に対する $i$ と $i^2+1\pmod{p}$ への辺 $p$ 本によるグラフ $G$ を考える．このとき，橋を何回渡っても行き来することができない $2$ つの異なる島が存在することは $G$ が連結でないことと同値である．$G$ が自己ループの頂点を $2$ つ持つとき，自己ループでない辺が $p-2$ 本あり，頂点数が $p$ であることと合わせれば $G$ は連結でない．従って以下の合同方程式が $2$ つの異なる解を持つような素数 $p$ が無数にあることを示せばよい．

$$n^2+1\equiv n\pmod{p}$$

この方程式は $m^2+3\equiv 0\pmod p$ と表せる．あとは $m$ から決め打ちして $p$ を構成すればよい．