メビウス関数 `mu(n)` とは自然数 (`n >= 1`) に対して、次のように定義される。
このとき、`mu(n)` の値を `n = 1` から `n = `nmax まで計算するプログラムを作る。
メビウス関数の応用例として円分多項式（円周等分多項式）の表示について述べる。 さて、`n` 次の円分多項式 `Phi_n(x)` は次で定義される。
`Phi_n(x) = prod_(gcd(k, n)=1) (x - zeta_n^k)`
ここで積は、与えられた `n` に対して `n` と互いに素である自然数 `k (1 <= k <= n)` すべてに対してとる。 また、`zeta_n` は次で定義され、`zeta_n^k` は `zeta_n` の `k` 乗である。すなわち、`zeta_n^k` は 1 の `n` 乗根である。
`zeta_n = exp ((2 pi i)/n)`
この定義式に基づいて円分多項式を求めるのは困難である。次の命題を使うのが求めやすい。
`n` を自然数とすると下記の等式が成り立つ。
`x^n - 1 = prod_(d|n) Phi_d(x)`
ここで右辺は、`n` の正の約数すべての `d` について多項式 `Phi_d(x)` を掛けることを表す。 この式を使っていけば、`Phi_1(x), Phi_2(x), cdots` を順に求めることができる。たとえば、
`x - 1 = Phi_1(x)`
`x^2 - 1 = Phi_1(x)Phi_2(x)`
`x^3 - 1 = Phi_1(x)Phi_3(x)`
`x^4 - 1 = Phi_1(x)Phi_2(x)Phi_4(x)`
`x^5 - 1 = Phi_1(x)Phi_5(x)`
`x^6 - 1 = Phi_1(x)Phi_2(x)Phi_3(x)Phi_6(x)`
これらから、次のように求めることができる。
`Phi_1(x) = x - 1`
`Phi_2(x) = (x^2 - 1) / (x - 1) = x + 1`
`Phi_3(x) = (x^3 - 1) / (x - 1) = x^2 + x + 1`
`Phi_4(x) = (x^4 - 1) / ((x - 1)(x + 1)) = x^2 + 1`
`Phi_5(x) = (x^5 - 1) / (x - 1) = x^4 + x^3 + x^2 + x + 1`
`Phi_6(x) = (x^6 - 1) / ((x - 1) (x + 1) (x^2 + x + 1)) = (x^4 + x^2 + 1) / (x^2 + x + 1) = x^2 - x + 1`
さらに、任意の `n` に関して直接円分多項式を表す式もある。それはメビウス関数を利用した式で、次で表される。
`Phi_n(x) = prod_(d|n) (x^d - 1) ^(mu (n / d))`
`n = 6` について具体的に表示する。
| `Phi_6(x)` | ` = (x^1 - 1) ^ (mu (6)) (x^2 - 1)^(mu (3)) (x^3 - 1)^(mu (2)) (x^6 - 1)^(mu (1))` |
| ` = ((x - 1) (x^6 - 1)) / ((x^2 - 1)(x^3 - 1))` | |
| ` = (x^3 + 1) / (x + 1)` | |
| ` = x^2 - x + 1` |
一見分子が分母で割り切れるか不安であるが、大丈夫だ。`Phi_n(x)` が `x` のモニック多項式であることは証明されている。
参考：多項式のクラス
まりんきょ学問所 ＞ JavaScript 手習い ＞ メビウス関数
