2. 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 2.21 (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 2.22 (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 2.23 (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.\]

Nhận xét 2.4

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.

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

Nhận xét 2.5

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\)	...	\((n-1)m + 1\)
\(2\)	\(m+2\)	...	\((n-1)m + 2\)
...	...	...	...
\(m\)	\(m+m\)	...	\((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.

Nhận xét 2.6

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

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

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)\]

Ta liên hệ một dạng biểu thức đơn giản là

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

hoặc với 3 biến là

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

Tổng quát 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\).

2.2. Định lý Euler

Định lí 2.5 (Đị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.

2.3. Định lý Fermat nhỏ

Định lí 2.6 (Đị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ì

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

Nhận xét 2.7

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