3. Các hàm số học quan trọng

3.1. Hàm Euler

Đầu tiên chúng ta xem xét hệ thặng dư đầy đủ và hệ thặng dư thu gọn.

Định nghĩa 3.19 (Hệ thặng dư đầy đủ)

Hệ thặng dư đầy đủ của số nguyên dương \(n\) là tập \(\mathbb{Z}_n = \{ 0, 1, \ldots, n-1 \}\).

Nói cách khác, hệ thặng dư đầy đủ của \(n\) là các số dư có thể có khi chia một số bất kì cho \(n\).

Định nghĩa 3.20 (Hệ thặng dư thu gọn)

Hệ thặng dư thu gọn của số nguyên dương \(n\) là tập các số \(a\) mà \(1 \leqslant a < n\) và \((a, n) = 1\).

\[\mathbb{Z}_n^{\times} = \{ a : 1 \leqslant a < n \ \text{và} \ (a, n) = 1 \}.\]

Định nghĩa 3.21 (Phi hàm Euler)

Cho số nguyên dương \(n\). Số lượng các số dương nhỏ hơn \(n\) và nguyên tố cùng nhau với \(n\) được kí hiệu bởi \(\varphi(n)\) và gọi là \(\varphi\) hàm Euler.

Nói cách khác, \(\varphi\) hàm Euler là số lượng phần tử trong tập \(\mathbb{Z}_n^{\times}\).

\[\varphi(n) = \lvert \mathbb{Z}_n^{\times} \rvert.\]

Chú ý 3.18

Nếu \(n\) là số nguyên tố thì \(\varphi(n) = n-1\).

Hàm Euler có ý nghĩa quan trọng trong lý thuyết số, công cụ giúp chúng ta giải các vấn đề về số mũ trong modulo.

3.1.1. Tính chất hàm Euler

Chú ý 3.19

Với \((m, n) = 1\) thì \(\varphi(m n) = \varphi(m) \varphi(n)\).

Chứng minh

Ta viết các số từ \(1\) tới \(mn\) thành bảng như sau

\(1\)	\(m+1\)	\(\ldots\)	\((n-1)m + 1\)
\(2\)	\(m+2\)	\(\ldots\)	\((n-1)m + 2\)
\(\ldots\)	\(\ldots\)	\(\ldots\)	\(\ldots\)
\(m\)	\(m+m\)	\(\ldots\)	\((n-1)m + m\)

Hàng \(r\) gồm các phần tử dạng \(r m + k\) với \(0 \leqslant r \leqslant n-1\) và \(1 \leqslant k \leqslant m\). Ta thấy rằng nếu \((rm + k, m) = 1\) thì \((k, m) = 1\).

Do đó trên mỗi hàng có \(\varphi(m)\) phần tử nguyên tố cùng nhau với \(m\).

Tiếp theo, trên các hàng vừa tìm được, do \((m, n) = 1\) nên để \((rm + k, n) = 1\) thì \((r, n) = 1\), nghĩa là có \(\varphi(n)\) hàng như vậy.

Tổng kết lại, ta có \(\varphi(m) \varphi(n)\) phần tử trong bảng nguyên tố cùng nhau với \(mn\). Do đó có điều phải chứng minh.

Do tính chất này nên hàm Euler là hàm nhân tính.

Chú ý 3.20

Cho số nguyên dương \(n\). Khi đó

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

Để chứng minh tính chất trên ta cần công thức khai triển

\[\prod_{i=1}^n (1 + x_i) = \sum_{\{ i_1, \ldots, i_k \} \subset I} x_{i_1} \cdots x_{i_k}\]

với \(I = \{ 1, \ldots, n \}\).

Khi \(n = 2\) ta có biểu thức đơn giản là

\[(1+x)(1+y) = 1+x+y+xy,\]

hoặc với \(n = 3\) biến là

\[(1+x)(1+y)(1+y) = 1 + x + y + z + xy + yz + yz + xyz.\]

Chứng minh

Giả sử phân tích thừa số nguyên tố của \(n\) là

\[n = p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k}.\]

Khi đó mỗi ước \(d\) của \(n\) đều có dạng \(p_1^{f_1} p_2^{f_2} \cdots p_k^{f_k}\) với \(0 \leqslant f_i \leqslant e_i\), \(i = 1, 2, \ldots, k\).

Như vậy

\[\sum_{d | n} \varphi(d) = \sum_{0 \leqslant f_i \leqslant e_i} \varphi\Big(p_1^{f_1} p_2^{f_2} \ldots p_k^{f_k}\Big) = \varphi\Big(p_1^{f_1}\Big) \varphi\Big(p_2^{f_2}\Big) \ldots \varphi\Big(p_k^{f_k}\Big)\]

Sử dụng công thức khai triển trên cho \(k\) biến ở trên thì biểu thức tương đương với

\[\begin{split}\sum_{0 \leqslant f_i \leqslant e_i} \varphi\left(p_1^{f_1}\right) \varphi\left(p_2^{f_2}\right) \ldots \varphi\left(p_k^{f_k}\right) = & (1 + \varphi(p_1) + \varphi(p_1^2) + \ldots + \varphi(p_1^{e_1})) \\ \times & (1 + \varphi(p_2) + \varphi(p_2^2) + \ldots + \varphi(p_2^{e_2})) \\ \times & \ldots \\ \times & (1 + \varphi(p_k) + \varphi(p_k^2) + \ldots + \varphi(p_k^{e_k})).\end{split}\]

Ở đây ta rút gọn dễ dàng với \(i = 1, 2, \ldots, k\):

\[\begin{split}& 1 + \varphi(p_i) + \varphi(p_i^2) + \ldots + \varphi(p_i^{e_i}) \\ = & 1 + p_i - 1 + p_i^2 - p_i + \ldots + p_i^{e_i} - p_i^{e_i-1} \\ = & p_i^{e_i}.\end{split}\]

Như vậy mỗi tổng \(1 + \varphi(p_i) + \cdots\) bằng chính \(p_i^{e_i}\). Nhân chúng lại với nhau ta có lại \(n\).

3.1.2. Định lý Euler

Định lý 3.18 (Định lý Euler)

Cho số nguyên dương \(n\). Với mọi số nguyên \(a\) mà \((a, n) = 1\) thì

\[\boxed{a^{\varphi(n)} \equiv 1 \pmod n.}\]

Chứng minh

Giả sử \(S = \{ a_1, a_2, \ldots, a_{\varphi(n)} \}\) là hệ thặng dư thu gọn của \(n\). Ta sẽ chứng minh rằng nếu \(a\) là số sao cho \((a, n) = 1\) thì tập hợp

\[\{ a a_1 \pmod n, a a_2 \pmod n, \ldots, a a_{\varphi(n)} \pmod n \}\]

là hoán vị của tập \(S\).

Thật vậy, giả sử \(a a_i \equiv a a_j \pmod n\) với \(1 \leqslant i, j \leqslant \varphi(n)\) và \(i \neq j\).

Do \((a, n) = 1\) nên tồn tại nghịch đảo \(a' \pmod n\) của \(a\). Nhân \(a'\) cho hai vế ta còn \(a_i \equiv a_j \pmod n\).

Nói cách khác, nếu \(a_i \not\equiv a_j \pmod n\) thì \(a a_i \not\equiv a a_j \pmod n\), suy ra tập

\[\{ a a_1, a a_2, \ldots, a a_{\varphi(n)} \}\]

là hoán vị của \(S\).

Ta nhân tất cả phần tử của \(S\) thì sẽ bằng tích phần tử của tập trên

\[a a_1 \cdot a a_2 \ldots a a_{\varphi(n)} \equiv a_1 \cdot a_2 \ldots a_{\varphi(n)} \pmod n.\]

Đặt \(I = a_1 \cdot a_2 \cdots a_{\varphi(n)}\) thì phương trình trên tương đương với

\[a^{\varphi(n)} \cdot I \equiv I \pmod n,\]

mà \((I, n) = 1\) do là tích các số nguyên tố cùng nhau với \(n\) nên rút gọn hai vế ta được

\[a^{\varphi(n)} \equiv 1 \pmod n.\]

Ta có điều phải chứng minh.

3.1.3. Định lý Fermat nhỏ

Định lý 3.19 (Định lý Fermat nhỏ)

Cho số nguyên tố \(p\). Với mọi số nguyên \(a\) thì

\[a^p \equiv a \pmod p.\]

Khi \((a, p) = 1\) thì

\[\boxed{a^{p-1} \equiv 1 \pmod p.}\]

Chú ý 3.21

Khi \((a, p) = 1\) thì định lý Fermat là hệ quả trực tiếp từ định lý Euler.

3.2. 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.

3.2.1. Hàm Möbius

Định nghĩa 3.22 (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\).

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

Tính chất 3.2

1. Nếu \(\gcd(n_1, n_2) = 1\) thì \(\mu(n_1 \cdot n_2) = \mu(n_1) \cdot \mu(n_2)\).

2. \(\sum\limits_{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.

3.2.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

(3.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 (3.1) tương đương:

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

mà \(\sum\limits_{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)}.\]

3.2.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 \(\sum\limits_{d \mid n} \varphi(d) = n\).