Định lý hàm phi Euler

Trong lý thuyết số học, hàm số Euler của một số nguyên dương n được định nghĩa là số lượng các số nguyên dương nhỏ hơn hoặc bằng n, mà nguyên tố cùng nhau với n ( ϕ ( n ) {\displaystyle \phi (n)} là số nguyên tố cùng nhau với n trong khoảng từ 1 đến n) . Hàm Euler được ký hiệu bằng $\mathrm{\varphi <!--\; \varphi \; -->}\left(n\right)$ hoặc $\mathrm{\phi <!--\; \phi \; -->}\left(n\right)$, do đó hàm này còn được gọi là hàm phi Euler.

Ví dụ, $\mathrm{\varphi <!--\; \varphi \; -->}\left(9\right)=6$ vì có sáu số 1, 2, 4, 5, 7 và 8 là nguyên tố cùng nhau với 9.

Hàm số $\mathrm{\varphi <!--\; \varphi \; -->}$ trong tiếng Anh còn được biết đến là hàm 'totient'.

Hàm này, còn được gọi là hàm số Euler theo tên nhà toán học Thụy Sĩ Leonhard Euler, người đã nghiên cứu và ký hiệu bằng chữ cái Hy Lạp Phi ($\mathrm{\varphi <!--\; \varphi \; -->}$). Đối totient của n là số các số nguyên dương nhỏ hơn hoặc bằng n mà không nguyên tố với n, được ký hiệu là $n-<!--\; -\; -->\mathrm{\varphi <!--\; \varphi \; -->}\left(n\right)$.

Hàm phi rất hữu ích vì nó đại diện cho kích thước của nhóm nhân các số nguyên modulo n. Quan trọng hơn, $\mathrm{\varphi <!--\; \varphi \; -->}\left(n\right)$ thể hiện cấp của nhóm đơn vị trong vành có đơn vị $Z/nZ$.

Tính giá trị hàm phi Euler

Công thức

Theo định nghĩa, chúng ta có $\mathrm{\varphi <!--\; \varphi \; -->}\left(1\right)=1$, và $\mathrm{\varphi <!--\; \varphi \; -->}\left(n\right)=(p-<!--\; -\; -->1)p^{k-<!--\; -\; -->1}$ khi n là lũy thừa của số nguyên tố p với bậc k ($n=p^k$). Hơn nữa, $\mathrm{\varphi <!--\; \varphi \; -->}$ là một hàm nhân tính; nếu m và n nguyên tố cùng nhau thì $\mathrm{\varphi <!--\; \varphi \; -->}\left(mn\right)=\mathrm{\varphi <!--\; \varphi \; -->}\left(m\right)\mathrm{\varphi <!--\; \varphi \; -->}\left(n\right)$. (Tóm tắt chứng minh: với A, B, C là các tập hợp lớp đồng dư theo m, n, mn; sẽ có một song ánh giữa $A\times <!--\; \times \; -->B$ và $C$, (theo [[định lý số dư Trung Quốc]]).) Giá trị của $\mathrm{\varphi <!--\; \varphi \; -->}\left(n\right)$ có thể được tính bằng định lý cơ bản số học.

Giả sử

$n=p_1^{k_1}\cdots <!--\; \cdots \; -->p_r^{k_r}$

với các $p_j$ là các số nguyên tố khác nhau, thì

$\mathrm{\phi <!--\; \phi \; -->}\left(n\right)=(p_1-<!--\; -\; -->1)p_1^{k_1-<!--\; -\; -->1}\cdots <!--\; \cdots \; -->(p_r-<!--\; -\; -->1)p_r^{k_r-<!--\; -\; -->1}$

Công thức này được gọi là tích Euler và thường được viết dưới dạng

$\mathrm{\phi <!--\; \phi \; -->}\left(n\right)=n\underset{p|n}{\prod <!--\; \prod \; -->}\left(1-<!--\; -\; -->\frac{1}{p}\right)$

với tích chạy qua tất cả các số nguyên tố $p$ là ước của $n$.

Ví dụ minh họa

$\mathrm{\phi <!--\; \phi \; -->}\left(36\right)=\mathrm{\phi <!--\; \phi \; -->}\left(3^2{2}^2\right)=36\left(1-<!--\; -\; -->\frac{1}{3}\right)\left(1-<!--\; -\; -->\frac{1}{2}\right)=36\cdot <!--\; \cdot \; -->\frac{2}{3}\cdot <!--\; \cdot \; -->\frac{1}{2}=12$

Các giá trị mẫu

100 giá trị đầu tiên trong dãy số A000010 từ bảng OEIS được trình bày dưới dạng bảng và đồ thị như sau:

φ(n) với 1 ≤ n ≤ 100

+	1	2	3	4	5	6	7	8	9	10
0	1	1	2	2	4	2	6	4	6	4
10	10	4	12	6	8	8	16	6	18	8
20	12	10	22	8	20	12	18	12	28	8
30	30	16	20	16	24	12	36	18	24	16
40	40	12	42	20	24	22	46	16	42	20
50	32	24	52	18	40	24	36	28	58	16
60	60	30	36	32	48	20	66	32	44	24
70	70	24	72	36	40	36	60	24	78	32
80	54	40	82	24	64	42	56	40	88	24
90	72	44	60	46	72	32	96	42	60	40

Đặc điểm

Số $\mathrm{\phi <!--\; \phi \; -->}\left(n\right)$ tương đương với số lượng phần tử sinh của nhóm cyclic $C_n$ (và do đó cũng là bậc của đa thức cyclotomic ${\mathrm{\phi <!--\; \phi \; -->}}_n$). Từ đó, mọi phần tử của $C_n$ sẽ tạo thành một nhóm con cyclic của $C_n$ và có dạng $C_d$ trong đó d là ước số của n (ký hiệu $d|n$), ta có

$\underset{d\mid <!--\; \mid \; -->n}{\sum <!--\; \sum \; -->}\mathrm{\phi <!--\; \phi \; -->}\left(d\right)=n$

điều này tương ứng với tổng của tất cả các ước dương d của n.

Chúng ta có thể áp dụng công thức đảo ngược Möbius để 'phản chuyển' tổng này và từ đó có được một công thức khác cho hàm $\mathrm{\phi <!--\; \phi \; -->}\left(n\right)$:

$\mathrm{\phi <!--\; \phi \; -->}\left(n\right)=\underset{d\mid <!--\; \mid \; -->n}{\sum <!--\; \sum \; -->}d\cdot <!--\; \cdot \; -->\mathrm{\mu <!--\; \mu \; -->}\left(n/d\right)$

trong đó $\mathrm{\mu <!--\; \mu \; -->}$ là hàm Möbius, xác định trên các số nguyên dương.

Theo Định lý Euler, nếu a là số nguyên tố cùng nhau với n, tức là ƯCLN(a,n) = 1, thì

$a^{\mathrm{\phi <!--\; \phi \; -->}\left(n\right)}\equiv <!--\; \equiv \; -->1\mathrm{mod}n.$

Điều này được rút ra từ Định lý Lagrange và từ việc a nằm trong nhóm nhân modulo $Z/nZ$ nếu và chỉ nếu a và n là nguyên tố cùng nhau.

Liên kết ngoài

• Miyata, Daisuke & Yamashita, Michinori, Hàm số logarithmic được suy ra từ hàm số Euler Lưu trữ ngày 14-07-2010 tại Wayback Machine
• Bordellès, Olivier, [https://web.archive.org/web/20071221223328/http://les-mathematiques.u-strasbg.fr/phorum5/read.php?5,359275,359275 Lưu trữ ngày 21-12-2007 tại Wayback Machine Các số nguyên tố cùng với q trong $[1,n]$]