MathLabs

第3問

n2+1n^2+1 が 2n+2n2n+\sqrt{2n} より大きい素因数を持つような正の整数 nn が無限に存在することを証明せよ。
ステップ 3/6: x^2 = -1 (mod p) という整除条件を t で書き直す
4(x2+1)≡(2t+1)2+4(modp)4(x^2+1)\equiv(2t+1)^2+4 \pmod p
詳しい解説

p∣x2+1p\mid x^2+1 より p∣4(x2+1)p\mid 4(x^2+1) でもある。x=p+12+tx=\frac{p+1}2+t を代入すると 4x2+4=(p+1+2t)2+44x^2+4=(p+1+2t)^2+4 となり、p+1+2t≡1+2t(modp)p+1+2t\equiv1+2t\pmod p であるから 4(x2+1)≡(2t+1)2+4(modp)4(x^2+1)\equiv(2t+1)^2+4\pmod p を得る。この合同式により tt の下からの評価が可能になる。