Hàm phi Euler, hay còn được gọi là hàm totient, là một khái niệm quan trọng trong Toán học, đặc biệt là trong Lý thuyết số. Được giới thiệu bởi nhà toán học Leonhard Euler vào thế kỷ 18, hàm phi Euler đóng vai trò then chốt trong việc giải quyết nhiều bài toán phức tạp và mở ra cánh cửa khám phá những bí ẩn ẩn giấu trong thế giới Toán học muôn màu.
Euler's totient function (Hàm phi Euler) ký hiệu là ϕ(n), đếm số các số nguyên dương nhỏ hơn hoặc bằng n và nguyên tố cùng nhau với n. Nói cách khác, nó đếm số lượng các số nguyên dương k trong khoảng 1 ≤ k ≤ n sao cho Ước số chung lớn nhất (ƯSCLN(n, k)) bằng 1.
Trường hợp n phân tích thành tích các số nguyên tố khác nhau:
ϕ(n) = n * ∏(1 - 1/p_i)
Trường hợp n là số nguyên tố:
ϕ(p) = p - 1
Có hai cách chính để tính hàm phi Euler (ϕ(n)) cho một số nguyên dương n. Đó là:
Sử dụng công thức:
Với d là ước chung lớn nhất của a và b
Ví dụ: Tính ϕ(60)
Giải:
Phân tích 60 thành tích các số nguyên tố: 60 = 2^2 * 3 * 5
Vì 60 là tích của ba số nguyên tố phân biệt nên ta áp dụng công thức thứ hai:
ϕ(60) = ϕ(2^2) * ϕ(3 * 5) = (2^2 - 1) * (3 - 1) * (5 - 1) = 3 * 2 * 4 = 24
Hàm phi Euler, ký hiệu là ϕ(n), là một hàm số quan trọng trong lý thuyết số học, được định nghĩa cho số nguyên dương n lớn hơn 1 là số lượng các số nguyên dương m nhỏ hơn hoặc bằng n và nguyên tố cùng nhau với n. Dưới đây là một số tính chất quan trọng của hàm phi Euler:
Tính chất đối với số nguyên tố: Nếu p là số nguyên tố, thì ϕ(p)=p−1.
Tính chất nhân: Nếu a và b là hai số nguyên dương nguyên tố cùng nhau, thì ϕ(ab)=ϕ(a)ϕ(b).
Tính chất với số mũ: Nếu p là số nguyên tố và k là số nguyên dương, thì:
Tính chất tổng quát: Nếu n là số nguyên dương và d là ước dương của n, thì:
Tính chất liên quan đến hàm Möbius:
Trong đó μ(d) là hàm Möbius.
Tính chất liên quan đến nghịch đảo modulo:
Nếu a và n nguyên tố cùng nhau, thì:
Tính chất liên quan đến ước chung lớn nhất: Nếu a và b là hai số nguyên dương, thì:
Trong đó gcd(a,b) là ước chung lớn nhất của a và b.
Tính chất liên quan đến số nguyên tố Carmichael: Một số nguyên dương n là số nguyên tố Carmichael khi và chỉ khi ϕ(n)=n−1.
Ví dụ:
Tính ϕ(10):
Phân tích 10 thành thừa số nguyên tố ta được 10=2*5. Do 2 và 5 nguyên tố cùng nhau nên ϕ(10)=ϕ(2)ϕ(5)=(2−1)(5−1)=4.
Tính ϕ(12):
Phân tích 12 thành thừa số nguyên tố ta được 12=2^2*3. Do 2 và 3 nguyên tố cùng nhau nên ϕ(12)=ϕ(2^2)ϕ(3)=(2^2−2^1)(3−1)=8.
Hàm phi Euler, còn được gọi là hàm totient, là một hàm số quan trọng trong số học có nhiều ứng dụng trong nhiều lĩnh vực khác nhau. Dưới đây là một số ứng dụng tiêu biểu:
Bài tập 1: Tính ϕ(n) cho các số nguyên dương sau:
Lời giải:
ϕ(20) = 20 * (1 - 1/2) * (1 - 1/5) = 8
ϕ(48) = 48 * (1 - 1/2) * (1 - 1/3) * (1 - 1/4) = 16
ϕ(105) = 105 * (1 - 1/3) * (1 - 1/5) * (1 - 1/7) = 24
Bài tập 2: Chứng minh rằng nếu a và b là hai số nguyên dương nguyên tố cùng nhau thì ϕ(ab) = ϕ(a) * ϕ(b).
Lời giải:
Gọi X={1,2,...,a−1,a+1,...,b−1,b+1,...,ab}.
Do đó, mỗi phần tử trong X nguyên tố cùng nhau với ab.
Vì X có ϕ(a)⋅ϕ(b) phần tử nên ϕ(ab)=ϕ(a)⋅ϕ(b).
Bài tập 3: Tính ϕ(n) với n=12.
Lời giải:
Phân tích n=12=2^2*3. Do 2 và 3 nguyên tố cùng nhau nên:
ϕ(12)=ϕ(2^2)⋅ϕ(3)=2*(2−1)*(3−1)=4.
Hàm phi của Euler, tuy chỉ là một hàm số số học đơn giản, lại ẩn chứa sức mạnh to lớn và ứng dụng rộng rãi trong nhiều lĩnh vực toán học, mật mã học và khoa học máy tính. Việc khám phá và nghiên cứu hàm phi Euler đã góp phần thúc đẩy sự phát triển của các ngành khoa học này, mở ra những hướng nghiên cứu mới đầy tiềm năng.
