Định lý Euler là khái quát hóa định lý Fermat nhỏ xử lý lũy thừa số nguyên modulo số nguyên dương. Nổi lên trong ứng dụng lý thuyết số sơ cấp, như khung lý thuyết hỗ trợ hệ mật mã RSA.
Định lý phát biểu: với mọi a và n nguyên tố cùng nhau:
aφ(n) ≡ 1 (mod n)
trong đó φ(n) là hàm Euler (totient function), đếm số nguyên dương < n nguyên tố cùng nhau với n.
Xét tập các số nguyên đó: R = {x₁, x₂, ... xφ(n)}, mỗi xᵢ là số nguyên dương duy nhất < n với gcd(xᵢ, n) = 1. Nhân mỗi phần tử với a và modulo n:
S = {(ax₁ mod n), (ax₂ mod n), ... (axφ(n) mod n)}
Vì a nguyên tố cùng n và xᵢ nguyên tố cùng n, axᵢ cũng nguyên tố cùng n. Do đó tất cả thành viên S là số nguyên < n và nguyên tố cùng n.
Không có trùng lặp trong S. Nếu axᵢ mod n = axⱼ mod n thì xᵢ = xⱼ.
Do đó ∏(axᵢ mod n) = ∏xᵢ (mod n)
aφ(n) × [∏xᵢ] ≡ ∏xᵢ (mod n)
aφ(n) ≡ 1 (mod n)
Hàm Euler Totient
Hàm Euler Totient là hàm nhân toán học đếm số nguyên dương đến số nguyên cho trước 'n' là số nguyên tố cùng 'n' và hàm dùng hiểu số lượng số nguyên tố tồn tại đến 'n'.
Còn gọi hàm phi Euler. Đóng vai trò thiết yếu trong mật mã học. Tìm số nguyên vừa < n vừa nguyên tố cùng n. Tập này ký hiệu Zn* (số < n và nguyên tố cùng n).
Hàm Euler totient hữu ích nhiều cách. Dùng trong hệ mã hóa RSA cho mục tiêu bảo mật. Hàm xử lý lý thuyết số nguyên tố, hữu ích tính toán lớn. Dùng tính toán đại số và số đơn giản.
Ký hiệu hàm là φ, cũng gọi hàm phi. Hàm có dùng lý thuyết hơn thực tế. Yêu cầu thực tế hạn chế.
Hàm hiểu tốt qua ví dụ thực tế thay vì chỉ lý thuyết. Có nhiều quy tắc tính φ(n), số khác nhau dùng quy tắc khác.
Hàm Euler totient φ(n) tính số phần tử Zn* bằng các quy tắc:
φ(1) = 0.
φ(P) = P-1 nếu P nguyên tố.
φ(m×n) = φ(m)×φ(n) nếu m,n nguyên tố cùng nhau.
φ(Pᵉ) = Pᵉ - Pᵉ⁻¹ (nếu P nguyên tố).
4 quy tắc kết hợp được giá trị φ(n), phân tích n = P₁ᵉ¹ × P₂ᵉ² × ... × Pₖᵉᵏ
φ(n) = (P₁ᵉ¹-P₁ᵉ¹⁻¹)(P₂ᵉ²-P₂ᵉ²⁻¹)...(Pₖᵉᵏ-Pₖᵉᵏ⁻¹)
Độ khó tìm φ(n) phụ thuộc độ khó phân tích thừa số n.