解説

方針・初手

割り切れる条件は、合同式で余りの条件に置き換える。

(1) では、$n$ を $5$ で割った余りごとに $n^2+1$ の余りを調べればよい。

(2) では、$p=a^2+1$ より

$$ a^2 \equiv -1 \pmod p

$$

であることを利用し、$n^2+1 \equiv 0 \pmod p$ を $n^2 \equiv a^2 \pmod p$ に変形する。

解法1

(1)

$n$ を $5$ で割った余りは $0,1,2,3,4$ のいずれかである。

それぞれの場合について $n^2+1$ を $5$ で割った余りを調べる。

$$ \begin{array}{c|ccccc} n \pmod 5 & 0 & 1 & 2 & 3 & 4 \\ \hline n^2 \pmod 5 & 0 & 1 & 4 & 4 & 1 \\ n^2+1 \pmod 5 & 1 & 2 & 0 & 0 & 2 \end{array}

$$

したがって、$n^2+1$ が $5$ の倍数であるのは、$n^2+1 \equiv 0 \pmod 5$ のときであり、それは $n \equiv 2,3 \pmod 5$ の場合に限られる。

よって、$n^2+1$ が $5$ の倍数であることと、$n$ を $5$ で割ったときの余りが $2$ または $3$ であることは同値である。

(2)

$p=a^2+1$ であるから、

$$ a^2+1 \equiv 0 \pmod p

$$

すなわち

$$ a^2 \equiv -1 \pmod p

$$

である。

まず、$n^2+1$ が $p$ の倍数であるとする。このとき

$$ n^2+1 \equiv 0 \pmod p

$$

より

$$ n^2 \equiv -1 \pmod p

$$

である。一方、上で見たように $a^2 \equiv -1 \pmod p$ なので、

$$ n^2 \equiv a^2 \pmod p

$$

が成り立つ。したがって

$$ n^2-a^2 \equiv 0 \pmod p

$$

であり、

$$ (n-a)(n+a) \equiv 0 \pmod p

$$

となる。

ここで $p$ は素数であるから、積 $(n-a)(n+a)$ が $p$ で割り切れるならば、

$$ n-a \equiv 0 \pmod p

$$

または

$$ n+a \equiv 0 \pmod p

$$

である。

よって、

$$ n \equiv a \pmod p

$$

または

$$ n \equiv -a \pmod p

$$

である。$-a \equiv p-a \pmod p$ だから、$n$ を $p$ で割った余りは $a$ または $p-a$ である。

逆に、$n$ を $p$ で割った余りが $a$ または $p-a$ であるとする。

**(i)**

$n \equiv a \pmod p$ のとき、

$$ n^2+1 \equiv a^2+1 \equiv p \equiv 0 \pmod p

$$

である。

**(ii)**

$n \equiv p-a \pmod p$ のとき、$p-a \equiv -a \pmod p$ だから、

$$ n^2+1 \equiv (-a)^2+1=a^2+1=p \equiv 0 \pmod p

$$

である。

したがって、いずれの場合も $n^2+1$ は $p$ の倍数である。

以上より、$n^2+1$ が $p$ の倍数であることと、$n$ を $p$ で割ったときの余りが $a$ または $p-a$ であることは同値である。

解説

(1) は平方数の余りを調べる基本問題である。$5$ で割った余りだけを考えれば十分で、$n$ そのものの大きさは関係ない。

(2) の中心は、$p=a^2+1$ から $a^2 \equiv -1 \pmod p$ を作ることである。すると、$n^2+1 \equiv 0 \pmod p$ は $n^2 \equiv a^2 \pmod p$ に変わり、差の平方として

$$ n^2-a^2=(n-a)(n+a)

$$

を利用できる。

ここで $p$ が素数であることが重要である。素数 $p$ が積を割り切るなら、そのどちらか一方を割り切る、という性質を使うためである。

答え

**(1)**

$n^2+1$ が $5$ の倍数であることと、$n$ を $5$ で割ったときの余りが $2$ または $3$ であることは同値である。

**(2)**

$p=a^2+1$ が素数であるとき、$n^2+1$ が $p$ の倍数であることと、$n$ を $p$ で割ったときの余りが $a$ または $p-a$ であることは同値である。