メビウス関数の定義

メビウス関数（Möbius function）μ(n)は、自然数nに対して以下のように定義されます：

\[ \mu(n) = \begin{cases} 1 & \text{if } n = 1 \\ (-1)^k & \text{if } n \text{ is the product of } k \text{ distinct primes} \\ 0 & \text{if } n \text{ has a squared prime factor} \end{cases} \]

具体例：

• μ(1) = 1
• μ(2) = -1（素数2）
• μ(3) = -1（素数3）
• μ(4) = 0（2の二乗を含む）
• μ(6) = 1（2と3の積）
• μ(10) = 1（2と5の積）
• μ(20) = 0（2の二乗を含む）

メビウス関数の性質と証明

1. 乗法性

互いに素な正の整数mとnに対して、以下が成り立ちます：

\[ \mu(mn) = \mu(m) \cdot \mu(n) \]

証明：

• いずれかが平方因子を持つ場合、μ(mn) = 0 かつ μ(m)μ(n) = 0
• いずれかが1の場合、μ(1) = 1 より明らか
• 両方が平方因子を持たず、互いに素な場合、素因数の個数を足し合わせることで成り立つ

2. 約数和の性質

自然数nに対して、以下が成り立ちます：

\[ \sum_{d \mid n} \mu(d) = \begin{cases} 1 & \text{if } n = 1 \\ 0 & \text{if } n > 1 \end{cases} \]

証明：

• n = 1 の場合、μ(1) = 1
• n > 1 の場合、n の正の約数のうち、平方因子を持たないものの個数とその符号を考慮すると、二項定理により総和は0になる

メビウスの反転公式とその証明

関数f(n)とg(n)が自然数上の関数で、以下の関係があるとします：

\[ g(n) = \sum_{d \mid n} f(d) \]

このとき、f(n)は以下の式で表されます：

\[ f(n) = \sum_{d \mid n} \mu\left(\frac{n}{d}\right) g(d) = \sum_{d \mid n} \mu(d) g\left(\frac{n}{d}\right) \]

証明：

g(n) の定義を用いて、f(n) を以下のように展開します：

\[ \begin{aligned} f(n) &= \sum_{d \mid n} \mu\left(\frac{n}{d}\right) g(d) \\ &= \sum_{d \mid n} \mu\left(\frac{n}{d}\right) \sum_{e \mid d} f(e) \\ &= \sum_{e \mid n} f(e) \sum_{d’ \mid \frac{n}{e}} \mu(d’) \end{aligned} \]

ここで、\(\sum_{d’ \mid \frac{n}{e}} \mu(d’)\) は、n = e の場合に1、それ以外は0となるため、f(n) = f(n) となり、証明されます。

具体例：オイラー関数への応用

オイラーのトーシェント関数φ(n)は、1からnまでの整数のうち、nと互いに素なものの個数を表します。

以下の関係が知られています：

\[ \sum_{d \mid n} \phi(d) = n \]

メビウスの反転公式を用いることで、φ(n)を以下のように表すことができます：

\[ \phi(n) = \sum_{d \mid n} \mu\left(\frac{n}{d}\right) d = \sum_{d \mid n} \mu(d) \cdot \frac{n}{d} \]

具体例：

• n = 6 の場合、正の約数は 1, 2, 3, 6
• μ(1) = 1, μ(2) = -1, μ(3) = -1, μ(6) = 1
• φ(6) = μ(1)×6 + μ(2)×3 + μ(3)×2 + μ(6)×1 = 6 – 3 – 2 + 1 = 2

これは、1から6までの整数のうち、6と互いに素な数（1と5）の個数と一致します。