Định lý Euler là sự tổng quát hóa việc xử lý định lý nhỏ của Fermat với lũy thừa của số nguyên modulo số nguyên dương. Nó tăng lên trong các ứng dụng của lý thuyết số cơ bản, chẳng hạn như cấu trúc hỗ trợ lý thuyết cho hệ thống mật mã RSA.
Định lý này phát biểu rằng với mọi a và n tương đối nguyên tố -
$$ \ mathrm {a ^ {\ phi \ left (n \ right)} \, \ Equiv \, 1 \ left (mod \, n \ right)} $$
trong đó ф (n) là hàm totient của Euler, đếm số lượng các số nguyên dương không hơn n tương đối nguyên tố với n.
Hãy xem xét tập hợp các số nguyên như vậy -
R ={x 1 , x 2 ,… X ф (n) }, tức là mỗi phần tử xi của R là số nguyên dương duy nhất nhỏ hơn nwith ged (xi, n) =1. Sau đó nhân từng phần tử với a và modulo n -
S ={(ax 1 mod n), (ax 2 mod n),… (ax ф (n) mod n)}
Vì a tương đối nguyên tố với n và x i tương đối nguyên tố đối với n, ax i cũng phải tương đối nguyên tố đến n. Do đó, tất cả các thành viên của S là các số nguyên nhỏ hơn n và tương đối nguyên tố với n.
Không có bản sao trong S.
Nếu ax i mod n và n =ax j mod n rồi đến x i =x j
$$ \ mathrm {Do đó, \, \ Pi _ {i =1} ^ {\ phi \ left (n \ right)} \ left (ax_ {i} \, mod \, n \ right) =\ Pi _ { i =1} ^ {\ phi \ left (n \ right)} \, x_ {i}} $$
$$ \ mathrm {\ Pi _ {i =1} ^ {\ phi \ left (n \ right)} \, ax_ {i} \ equiv \ Pi _ {i =1} ^ {\ phi \ left (n \ phải)} \, x_ {i} \ left (mod \, n \ right)} $$
$$ \ mathrm {a ^ {\ phi \ left (n \ right)} \, x \ left [\ Pi _ {i =1} ^ {\ phi \ left (n \ right)} \, x_ {i} \ right] =\ Pi _ {i =1} ^ {\ phi \ left (n \ right)} \, x_ {i} \ left (mod \, n \ right)} $$
$$ \ mathrm {a ^ {\ phi \ left (n \ right)} \ equiv 1 \ left (mod \, n \ right)} $$
Chức năng Euler Totient
Hàm Totient của Euler là các hàm nhân toán học đếm số nguyên dương lên đến số nguyên đã cho thường được gọi là 'n' là một số nguyên tố của 'n' và hàm có thể được sử dụng để hiểu số lượng các số nguyên tố ex i lên đến số nguyên đã cho ‘n’.
Hàm Euler’s Totient còn được gọi là hàm Euler’s phi. Nó đóng một vai trò thiết yếu trong mật mã. Nó có thể phát hiện ra số lượng các số nguyên vừa nhỏ hơn n vừa tương đối nguyên tố với n. Tập hợp các số này được xác định bởi $ \ mathrm {Z_ {n} ^ {*}} $ (số nhỏ hơn n và tương đối nguyên tố với n).
Chức năng trang điểm của Euler có lợi theo một số cách. Nó có thể được sử dụng trong hệ thống mã hóa RSA, có thể được sử dụng cho các mục tiêu bảo mật. Hàm liên quan đến lý thuyết số nguyên tố, và nó cũng có lợi trong việc tính toán các phép tính lớn. Hàm có thể được sử dụng trong tính toán đại số và các số đơn giản.
Ký hiệu được sử dụng để biểu thị hàm là ϕ, và nó còn được gọi là hàm phi. Chức năng bao gồm sử dụng lý thuyết nhiều hơn thay vì sử dụng thực tế. Yêu cầu hợp lý của chức năng bị hạn chế.
Chức năng có thể được hiểu rõ hơn thông qua một số ví dụ thực tế thay vì chỉ giải thích lý thuyết. Có một số quy tắc để tính toán hàm Euler’s totient và đối với các số khác nhau, các quy tắc khác nhau sẽ được sử dụng.
Hàm Euler totient ф (n) tính số phần tử trong $ \ mathrm {Z_ {n} ^ {*}} $ với sự trợ giúp của các quy tắc sau -
-
ф (1) =0.
-
ф (P) =P - 1 nếu P là Nguyên tố.
-
ф (m x n) =ф (m) x ф (n) nếu m và n tương đối nguyên tố.
-
ф (P e ) =P e - P e − 1 (nếu P là số nguyên tố.)
Bốn quy tắc sau có thể được kết hợp để thu được giá trị của ф (n), phân tích nhân tử là
$$ \ mathrm {n =P_ {1} ^ {e1} \, x \, P_ {2} ^ {e2} x \ cdot \ cdot \ cdot P_ {k} ^ {ek}} $$
$$ \ mathrm {\ phi \ left (n \ right) =\ left (P_ {1} ^ {e1} -P_ {1} ^ {e1-1} \ right) \ left (P_ {2} ^ {e2 } -P_ {2} ^ {e2-1} \ right) x \ cdot \ cdot \ cdot x \ left (P_ {k} ^ {ek} -P_ {k} ^ {ek-1} \ right)} $ $
Độ khó của việc tìm ф (n) phụ thuộc vào độ khó của việc tìm thừa số củan.