✨Hàm phi Euler

nhỏ|phải|1000 giá trị đầu tiên của $\backslash 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 ( $\backslash phi(n)$ là số lượng số nguyên tố cùng nhau với n trong đoạn từ 1 đến n) . Hàm Euler được ký hiệu bởi $\backslash phi(n)$ hoặc $\backslash varphi(n)$, do đó hàm được gọi làm hàm phi Euler.

Chẳng hạn, $\backslash 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ố $\backslash phi$ 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 ($\backslash phi$). Đối totient của n được định nghĩa là $n\; -\; \backslash 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 $\backslash phi(n)$ là cấp của nhóm các đơn vị trong vành có đơn vị $\backslash mathbb\{Z\}/n\backslash mathbb\{Z\}$.

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

Công thức

Từ định nghĩa chúng ta có $\backslash phi(1)\; =\; 1$, và $\backslash 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 ($n=p^k$) . Ngoài ra, $\backslash phi$ là một hàm nhân tính; nếu m và n là nguyên tố cùng nhau thì $\backslash phi(mn)\; =\; \backslash phi(m)\; \backslash phi(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 $A\; \backslash times\; B$ và $C$, (theo định lý thặng dư Trung Hoa]).) Giá trị của $\backslash phi(n)$ có thể tính được khi sử dụng định lý cơ bản của số học: :Nếu

:$n\; =\; p\_1^\{k\_1\}\; \backslash cdots\; p\_r^\{k\_r\}$

trong đó các $p\_j$ là các số nguyên tố phân biệt, thì

:$\backslash varphi(n)=(p${1}-1)p{1}^{k{1}-1} \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à :$\backslash varphi(n)=n\backslash prod\_\{p|n\}\backslash left(1-\backslash frac\{1\}\{p\}\backslash right)$ với tích chạy qua các số nguyên tố $p$ là ước của $n$.

Ví dụ

:$\backslash varphi(36)=\backslash varphi\backslash left(3^2\; 2^2\backslash right)=36\backslash left(1-\backslash frac\{1\}\{3\}\backslash right)\backslash left(1-\backslash frac\{1\}\{2\}\backslash right)=36\backslash cdot\backslash frac\{2\}\{3\}\backslash cdot\backslash frac\{1\}\{2\}=12$

Một số giá trị

100 giá trị đầu tiên được hiển thị trong bảng và đồ thị dưới đây:

thumb|Đồ thị 100 giá trị đầu tiên :

Các tính chất

Số $\backslash varphi(n)$ cũng bằng số các phần tử sinh có thể của nhóm cyclic $C\_n$ (và do đó cũng là bậc của đa thức cyclotomic $\backslash varphi\_n$). Từ đó mọi phần tử của $C\_n$ sinh ra một nhóm con cyclic của $C\_n$ va có dạng $C\_d$ trong đó d là ước số của n (ký hiệu $d\; |\; n$), ta có :$\backslash sum\_\{d\backslash mid\; n\}\backslash 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 $\backslash varphi(n)$:

:$\backslash varphi(n)=\backslash sum\_\{d\backslash mid\; n\}\; d\; \backslash cdot\; \backslash mu(n/d)$

trong đó $\backslash 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ì :$a^\{\backslash varphi(n)\}\; \backslash equiv\; 1\backslash mod\; n.$ Điều này suy ra từ Định lý Lagrange và từ việc a thuộc nhóm nhân modulo $\backslash mathbb\{Z\}/n\backslash mathbb\{Z\}$ khi và chỉ khi a nguyên tố cùng nhau với n.