東大2019理系4

問題：

この問題は QuizKnock でも取り上げられている。

発想：

(1) はユークリッドの互除法。(2) は (1) を活用。

n^2 の mod 4 が 0 または 1 であることを知っていると便利。

n^2 + 1 が平方数でないことを n^2 < n^2+1 < (n+1)^2 を用いて示せるのは初見だった。

解答：