Hàm phi Euler – Wikipedia tiếng Việt

1000 giá trị đầu tiên của ${displaystyle phi (n)}$

Trong lý thuyết số, hàm số Euler của một số nguyên dương n được định nghĩa là số các số nguyên dương nhỏ hơn hoặc bằng n nguyên tố cùng nhau với n. Hàm Euler được ký hiệu bởi ${displaystyle phi (n)}$ hoặc ${displaystyle varphi (n)}$, do đó hàm được gọi làm hàm phi Euler.

Chẳng hạn, ${displaystyle phi (9)=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ố ${\displaystyle \mathrm{\varphi <!--\; \varphi \; -->}}$ trong tiếng Anh còn được gọi là hàm "totient".

Hàm này thường đượ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 nó và ký hiệu nó bằng chữ cái Hy Lạp Phi (${displaystyle phi }$). Đối totient của n được định nghĩa là ${displaystyle n-phi (n)}$, nghĩa 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.

Hàm phi có nhiều ứng dụng vì nó là kích thước của nhóm nhân các số nguyên modulo n. Quan trọng hơn ${displaystyle phi (n)}$ là cấp của nhóm các đơn vị trong vành có đơn vị ${displaystyle mathbb {Z} /nmathbb {Z} }$.

Công thức[sửa | sửa mã nguồn]

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

Nếu

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

trong đó các ${displaystyle p_{j}}$ là các số nguyên tố phân biệt,
thì

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

Công thức này là một tích Euler và thường được viết là

${displaystyle varphi (n)=nprod _{p|n}left(1-{frac {1}{p}}right)}$

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

Ví dụ[sửa | sửa mã nguồn]

${\displaystyle \mathrm{\phi <!--\; \phi \; -->}(36)=\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}$

Một số giá trị[sửa | sửa mã nguồn]

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

Số ${\displaystyle \mathrm{\phi <!--\; \phi \; -->}(n)}$ cũng bằng số các phần tử sinh có thể của nhóm cyclic ${\displaystyle C_n}$ (và do đó cũng là bậc của đa thức cyclotomic ${\displaystyle {\mathrm{\phi <!--\; \phi \; -->}}_n}$). Từ đó mọi phần tử của ${displaystyle C_{n}}$ sinh ra một nhóm con cyclic của ${displaystyle C_{n}}$ va có dạng ${displaystyle C_{d}}$ trong đó d chia hết n (ký hiệu ${displaystyle d|n}$), ta có

${displaystyle sum _{dmid n}varphi (d)=n}$

trong đó tổng trải trên tất cả các ước dương d của n.

Chúng ta cũng có thể sử dụng công thức đảo ngược Möbius để "đảo ngược" tổng này và được một công thức khác đối với hàm ${displaystyle varphi (n)}$:

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

trong đó ${displaystyle 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 nguyên tố cùng nhau với n, nghĩa là, ƯCLN(a,n) = 1, thì

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

Điều này suy ra từ Định lý Lagrange và từ việc a thuộc nhóm nhân modulo ${\displaystyle \mathbb{Z}/n\mathbb{Z}}$ nếu và chỉ nếu a nguyên tố cùng nhau với n.