>>39
まず素因数分解する
n = Π{i=1..t} p[i]^e[i]
素因数 2 は数え上げに寄与しないので、
最初から p[i]は奇素数, p[i] ≡ ±1 (mod 4) と考えても一般性を失わない。
さらに、-1 (mod 4) になる素因数は前方に集め置いて s個あるとする。
nの約数は
d = Π{i=1..t} p[i]^k[i] (k[i] = 0...e[i])
で尽くされる。
d ≡ Π{i=1..s} (-1)^k[i] ≡ (-1)^{ k[1]+k[2]+...+k[s] } (mod 4)

k[1]+k[2]+...+k[s]が偶(奇) となる場合の数を Ev[s]　(Od[s])
k[s]が偶(奇) となる場合の数を ev　(od)
と置く。
e[s]=2m, k[s]=0...2m なら ev=#{0,2,4,..,2m}=m+1, od=#{1,3,..,2m-1}=m
e[s]=2m+1, k[s]=0...2m+1 なら ev=#{0,2,4,..,2m}=m+1, od=#{1,3,..,2m+1}=m+1
よって
ev ≧ od

明らかに
Ev[s] = Ev[s-1]*ev + Od[s-1]*od
Od[s] = Ev[s-1]*od + Od[s-1]*ev

帰納法より
Ev[s] - Od[s] = (Ev[s-1] - Od[s-1]) (ev - od) ≧ 0
∴ Ev[s] ≧ Od[s] (p[s+1]以降の寄与はEv,Od共通で倍率かかるので無視した)
Q.E.D.