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

さてずいぶんだらだらと続けているシリーズですが、もうすぐ終わります。たぶん。

実は始めた当初は、前回までの内容しかできていませんでしたが、どうやらそれなりに形になりそうな気がしてきました。

問題設定

前回のエントリを書いた後、少し面倒なことを見つけたので条件を追加します。U(n, d, i) を考えるとき、今までは特に n, d, i について何も条件をつけませんでしたが、以下では n > 1 と gcd(n, d) = 1 を仮定することにします。これまでに書いた議論も実はこれに近い条件がないと嘘でした。

というわけで問題は以下。

n, d, i は自然数で $n > 1,\, \gcd(n, d) = 1$ とする。集合 $U(n, d, i) = \{x \mid in/d < x < (i+1)n/d,\; \gcd(n, x) = 1\}$ の元の個数を求めよ。

n の素因子を減らす

今回は、n が square-free であるとして、n の素因数を減らす方法を与えます。

p は素数、m は p で割り切れない 2 以上の自然数、n = pm としましょう。

前回の

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

と同様の考え方で U(pm, d, i) を分解します。今回は p で割り切れるところを引かなければならないので

$U(pm, d, i) = \left(\bigcup_{j = 0}^{p - 1} U(m, d, pi + j)\right) \setminus pU(m, d, i)$ ,
$pU(m, d, i) = \{px \mid im/d < x < (i+1)m/d,\; \gcd(m, x) = 1\}$

となります。ここで登場人物の包含関係を吟味すると次の等式が得られます。

$| U(pm, d, i) | = \sum_{j = 0}^{p - 1} | U(m, d, pi + j) | - | U(m, d, i) |$