互いに素な数を数える (4)

今回は、n が平方因子を含む場合を含まない場合に帰着できることを示します。前回 http://d.hatena.ne.jp/lkozima/20090128/1233155371 の簡単な一般化です。

前回の最後に

$U(4k, 3, i) = U(2k, 3, 2i) \cup U(2k, 3, 2i+1)$

に言及しましたが、これは $lk \not | n$ ならばもっと一般化できて

$U(l^2k, d, i) = U(lk, d, li) \cup U(lk, d, li+1) \cup \cdots \cup U(lk, d, li + l - 1)$

が成り立ちます。右辺は disjoint union なので、この式から

$| U(l^2k, d, i) | = \sum_{j = 0}^{l - 1} | U(lk, d, li + j) |$

がわかります。これで平方因子を持たない場合に還元されました。ついでにこの等式は

$| U(l^2k, d, i) | = \sum_{j = 0}^{l - 1} | U(lk, d, (li + j) % d) |$

と変形できることにも注意しておきます。これは、

$x \in U(n, d, i) \Leftrightarrow x + n \in U(n, d, i + d)$

から出てくる等式 $| U(n, d, i) | = | U(n, d, i + d) |$ を使うとすぐに分かります。