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

d = 3 の場合で一番簡単なのが n が3 でない素数の場合です。これをまずやってみます。

まず最初に次のことに注意します。

n が素数のとき、0 < x < n なる x はすべて n と互いに素

単なる素数の定義ですが、このことから n が素数のとき今考えている問題は「区間 (0, n) を三等分したときにそれぞれの区間にいくつの整数が含まれるか」という問題と同じであることがわかります。

というわけで $|U(n, 3, i)|$ は区間を三等分したそれぞれの部分にある整数の個数なので、以下のように表せます。

もう少し計算を進めてみます。n = 2, 3 のときは具体的に計算すればできるので、n > 3 を仮定しましょう。5 以上の素数は 6 で割ると 1 または 5 余ることから $n = 6k + 1$ と $n = 6k + 5$ の二通りが考えられます。

普通に計算するだけ。 $2k,\; 2k,\; 2k$ となります。

こっちも計算するだけ。今度は $2k+1,\; 2k+2,\; 2k+1$ です。