プロジェクトオイラー
http://projecteuler.net/index.php?section=problems&id=272
C(n)の求め方を勘違いしていて、間違いに気がついたのが昨日の夜で、これで簡単になるじゃんと思ってコードを書いたんだが、最初個数だと思ってしまって、書き直して和にしたら返ってこなくなった。さっき少しコードを変えたら返ってきた。
ここからひとりごと。
今日30kmジョグしながらC(n)について考えていた。
C(n)の代わりに、範囲を 0≤x<n としたD(n)を考える。
まず、D(n)は乗法的、すなわち、m、nが互いに素であるとき、D(mn) = D(m)D(n)が成り立つことはすぐに分かる。よって、素数あるいはそのべきのときだけ考えればよい。
y = x + 1
とすると、
y(y2 + 3y + 3) ≡ 0(mod n) (0 ≤ y < n)
を考えることになる。
D(3) = 1は明らか。n = 3e (e ≥ 2)とすると、yが3e-1の倍数でなければならないのは明らかだから、D(3e) = 3。
y2 + 3y + 3 は奇数だから、D(2e) = 1。
さて、このくらいはジョグしながらぼんやり考えていてもすぐにわかる。問題はその他の場合だ。n = pe のとき、yがpの倍数なら y2 + 3y + 3 はpの倍数でないことが分かる。すなわち、
y2 + 3y + 3 ≡ 0(mod n)
となる。
(2y + 3)2 ≡ -3(mod n)
だから、
z2 ≡ -3(mod n)
に帰着される。
さて、ここからが相互法則の出番である。相互法則等を記憶していないのでジョグしながらはここまでだった。以下、ルジャンドルの記号（の簡略版）を使う。
n = p = 3k + 1
のとき、
(-1/p) = (-1)(p-1)/2
(-3/p) = (-1/p)(3/p)
(3/p)(p/3) = (3/p)(1/3) = (3/p) = (-1)(p-1)/2
(-3/p) = (-1/p)2 = 1
だから解がある。一方、
n = p = 3k + 2
のとき、
(p/3) = (2/3) = -1
が違うだけだから、
(-3/p) = -1
解は常にペアになっている。すなわち、zとz + kが解なら、
(z + k)2 - z2 = k(2z + k) ≡ 0(mod p)
だから、kは0とあともう一つしかない。
最後に、n = pe (e ≥ 2) のとき。pが3の剰余が2のときは明らか。
それ以外のとき、例えば、n = 73のとき。7で割って-3余る解は2*49個ある。さきほどと同じように、
k(2z + k) ≡ 0(mod n)
を考えると、kはやっぱり2つしかない。よって、2*49個は、73の剰余で49通りの値を持つ。7で割って-3余る値は49通りしかないから、そのうち2つが解である。
以上で全部分かったかな。
