素数全書練習問題1.10、1.11 - Finite Groups Fun 有限群あるいはちょこっと計算ファンの日記

まず、N以下の正整数で、有限素数列 $q_1,\quad q_2,\cdots,q_n$ のいずれかで割り切れるものの数が $\sum_{i=1}^n [\frac{N}{q_i}\$ -\sum_{i0.22857\cdots]である。

さて、後半。 $\mathcal{S}$ の逆数の和が発散するとして、 $\mathcal{S}$ の任意の有限部分列 $\mathcal{S}'$ を作ると先の議論と同様にして、 $\mathcal{A}$ の漸近密度が $e^{-S'}$ で抑えられることがわかる。 $S'\to \infty$ にできるので $\mathcal{A}$ の漸近密度は0である。

最後の部分。この問題のキモは、

｛2つの互いに素な整数の二乗和で書ける整数}⊂｛全てのmod 4で3になる素数で割り切れない正整数}

が成立していることで、これを認めると『mod 4で3になる素数の逆数の和は発散する』を既知として『全てのmod 4で3になる素数で割り切れない正整数』の集合の漸近密度が0になるため、より小さな『2つの互いに素な整数の二乗和で書ける整数』の集合の漸近密度が0になることがわかる。

さて、先の包含関係を証明する。2つの互いに素な正整数をa,bとして $a^2+b^2$ の任意の素因子をpとする。このときp=2あるいは $p\equiv 1(mod\quad 4)$ が証明できればよい。
まず、 $b\not\equiv 0(mod\quad p)$ である（∵そうでないとaとbは共通の素因子pを持ってしまう）。そこで mod pの世界ではbは逆数を持ち、 $x\equiv ab^{-1}(mod\quad p)$ なる正整数xが存在する。さらに、

$x^2+1 \equiv b^{-2}(a^2+b^2) \equiv 0 (mod\quad p)$

であるから、 $x^2 \equiv -1 (mod\quad p)$ となり、p≠2ならば xのmod pの世界での位数は4となる。一方で、mod pの世界の可逆元のなす群の位数はp-1であったから、有限群論での『有限群Gの部分群Hの位数はGの位数を割り切る』というラグランジュ(Lagrange)の定理から、 $4\mid (p-1)$ すなわち $p\equiv 1(mod\quad 4)$ が証明された。□

問題1.11については、すでに1.10の真ん中あたりで証明した結果をそのまま使えばよい。