問題はこちら。
いきなり mod p2 で考えるのはしんどいので、mod p から考える。
f(n)=n2−3n−1≡0 (mod p)
このような n,p の組が見つかった時、以下も成立することが分かる。
f(n±pk)=(n±pk)2−3⋅(n±pk)−1≡n2−3n−1≡0 (mod p)
以上より、n2−3n−1≡0 (mod p) なる n,p の組があるならば、1≤p<n も成立する。次に mod p2 について考える。
f(m)=m2−3m−1≡0 (mod p2)f(m=n+pk)=(n+pk)2−3⋅(n+pk)−1≡n2+2npk+p2k2−3n−3pk−1≡2npk−3pk+n2−3n−1≡(2n−3)pk+(n2−3n−1)≡0 (mod p2)
この時、n2−3n−1≡0 (mod p) であるので、両辺を p で割り
(2n−3)pk/p+(n2−3−1)/p≡0 (mod p2/p)(2n−3)k+(n2−3n−1)/p≡0 (mod p)
この 1 次合同式を解くことで k を得られ、f(m=n+pk)≡0 (mod p2) なる m も得られる。そして同様に p3,p4,... の場合も計算可能なことより、以上のこれらの性質から、篩を使うことで N までの区間に存在する素数を、高速に列挙可能でもあることが分かる。
なお、f(n)=n2−3n−1≡0 (mod p) なる n を 1 つ求められているならば
f(p−n+3)=(p−n+3)2−3⋅(p−n+3)−1≡n2−2np−3n+p2+3p−1≡n2−3n−1≡0 (mod p)
より、もうひとつの p で割り切れる系列を見つけ出すことができる。ただし
f(n=8)=39≡0 (mod p=13)p−n+3=13−8+3=8
のようなパターンもあるため、少しの注意が必要となる。また、mod p=13 については
(2⋅8−3)k+39/13≡0 (mod 13)13k+3≡0 (mod 13)3≠0
と、k が消えてしまうことから、f(13k+8)≡0 (mod 132) なる k は存在しないことも分かる。
自分の中では普通に解いたつもりだけど、他の人の解き方はわりと違うようだった。なんでや。
