第3問

n^2+1

が

2n+\sqrt{2n}

より大きい素因数を持つような正の整数

n

が無限に存在することを証明せよ。

ステップ 2/6: 剰余の上半分から x^2 = -1 (mod p) を満たす x を選ぶ

前のステップ次のステップ

p\equiv1\pmod4 \implies \exists\, x\in(\tfrac p2,p),\ x^2\equiv-1\pmod p; \quad x=\tfrac{p+1}2+t,\ t\ge0

詳しい解説

$p\equiv1\pmod8$ から $p\equiv1\pmod4$ が従うので、 $-1$ は $p$ を法とする平方剰余であり、ある整数の2乗が $-1\pmod p$ となる。その（和が $p$ になる）法 $p$ での2つの平方根のうち、 $\frac p2<x<p$ を満たす方を $x$ とする。整数 $t\ge0$ を用いて $x=\frac{p+1}2+t$ と書く。