4. Hàm Möbius¶

August Ferdinand Möbius là nhà toán học người Đức, đóng góp nổi tiếng của ông là dải Möbius. Tuy nhiên ở đây chúng ta xem xét một hàm số học mang tên ông.

Hàm Möbius đóng vai trò quan trọng trong việc tính các đại lượng liên quan tới số học.

4.1. Hàm Möbius¶

Định nghĩa 4.8 (Hàm Möbius)

Hàm Möbius của số nguyên dương \(n\) được định nghĩa như sau:

\[\begin{split}\mu (n) = \begin{cases} 1, \quad & \text{nếu} \ n = 1 \\ (-1)^k, \quad & \text{nếu} \ n = p_1 p_2 \ldots p_k \text{ với } p_i \text{ là các số nguyên tố khác nhau} \\ 0, \quad & \text{trong các trường hợp còn lại}. \end{cases}\end{split}\]

Điều này có nghĩa là, nếu \(n\) là tích của các số nguyên tố bậc \(1\) thì \(\mu (n) = (-1)^k\) với \(k\) là số lượng số nguyên tố trong tích. Như vậy, nếu tồn tại số nguyên tố \(p\) sao cho \(p^2 \mid n\) thì \(\mu(n) = 0\).

4.2. Tính chất hàm Möbius¶

Tính chất 4.2

Nếu \((n_1, n_2) = 1\) thì \(\mu(n_1 \cdot n_2) = \mu(n_1) \cdot \mu(n_2)\).
\(\displaystyle{\sum_{d \mid n} \mu(d) = 0}\) với \(n = p_1 p_2 \ldots p_k\).

Chứng minh

Với tính chất 1, ta dễ thấy rằng do \(n_1\) và \(n_2\) nguyên tố cùng nhau nên trong cách phân tích thừa số nguyên tố của chúng sẽ chứa các số nguyên tố khác nhau.

Khi đó \(\mu(n_1)\) và \(\mu(n_2)\) không bị phụ thuộc nhau và có thể tách thành phép nhân như trên.

Với tính chất 2, chúng ta lần lượt chọn \(d\) là tổ hợp của \(0\), \(1\), \(2\), ..., \(k\) số nguyên tố:

nếu \(d = 1\) thì \(\mu(d) = 1\);
nếu \(d = p_i\) thì \(\mu(d) = (-1)^1 = -1\) với \(i = \overline{1, k}\);
nếu \(d = p_i p_j\) với \(i \neq j\) thì \(\mu (d) = (-1)^2 = 1\);
tương tự như vậy, nếu \(d\) là tích của \(t\) số nguyên tố thì \(\mu (d) = (-1)^t\).

Ở mỗi trường hợp trên, do \(d\) là tổ hợp của \(t\) số nguyên tố (\(0 \leqslant t \leqslant k\)) nên số cách chọn số nguyên tố \(p_i\) ở mỗi trường hợp là \(C^t_k\). Ta cộng tất cả chúng lại

\[\sum_{d \mid n} \mu(d) = 1 - C^1_k + C^2_k - \ldots + (-1)^k C^k_k = 0\]

theo nhị thức Newton. Từ đó ta có điều phải chứng minh.

4.3. Công thức nghịch đảo Möbius¶

Giả sử ta có hai hàm \(f\) và \(g\) từ \(\mathbb{N}\) tới \(\mathbb{Z}\). Khi đó hai cách biểu diễn sau là tương đương.

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

Nghĩa là nếu chúng ta có hai hàm số \(f\) và \(g\) thỏa phương trình đầu (biểu diễn \(f\) theo \(g\)) thì chúng ta cũng sẽ tìm được cách biểu diễn \(g\) theo \(f\).

Chứng minh

Với \(d \mid n\), đặt \(d' = \dfrac{n}{d}\), suy ra \(d = \dfrac{n}{d'}\).

Như vậy \(f(d) \cdot \mu\left(\dfrac{n}{d}\right) = f \left(\dfrac{n}{d'}\right) \cdot \mu(d')\).

Ta lấy tổng lại thì

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

Ở đây lưu ý rằng nếu \(d\) là ước của \(n\) thì \(d' = \dfrac{n}{d}\) cũng là ước của \(n\). Do đó ta hoàn toàn có thể thay thế \(d'\) bởi \(d\) trong tổng trên.

Vì \(f(n) = \displaystyle{\sum_{d \mid n} g(d)}\) nên

(4.1)¶\[\sum_{d \mid n} f\left(\frac{n}{d}\right) \cdot \mu(d) = \sum_{d \mid n} \mu(d) \sum_{d' \mid \frac{n}{d}} g(d').\]

Dễ thấy rằng do \(d \mid n\) và \(d' \mid \dfrac{n}{d}\) nên tồn tại \(k\), \(l\) sao cho \(kd = n\) và \(ld' = \dfrac{n}{d}\). Khi đó \(n = ldd'\) và \(kd = n\), suy ra \(d' \mid n\) và \(d \mid \dfrac{n}{d'}\).

Tương tự như trên, ta có thể thay thế \(d\) bởi \(d'\) và ngược lại, phương trình (4.1) tương đương:

\[\sum_{d' \mid n} g(d') \sum_{d \mid \frac{n}{d'}} \mu(d),\]

mà \(\displaystyle{\sum_{a \mid p} \mu(a) = 0}\) nếu \(p \neq 1\) và bằng \(1\) với \(p = 1\) (đã chứng minh ở trên) nên từ đây suy ra

\[\sum_{d' \mid n} g(d') \sum_{d \mid \frac{n}{d'}} \mu(d) = \sum_{d' \mid n} g(d') \cdot 1 \,(\text{khi } n = d') = g(n).\]

Tương tự ta cũng có công thức nghịch đảo Möbius đối với phép nhân

\[f(n) = \prod_{d \mid n} g(d) \Longleftrightarrow g(n) = \prod_{d \mid n} f(d)^{\mu\left(\frac{n}{d}\right)}.\]

4.4. Liên hệ với hàm Euler¶

Nếu ta chọn \(f(n) = n\) và \(g(n) = \varphi(n)\) thì theo công thức nghịch đảo Möbius ta có

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

do ta đã biết \(\displaystyle{\sum_{d \mid n} \varphi(d) = n}\).