Định lý Euler

Định lý Euler chỉ ra rằng nếu n là một số nguyên dương bất kỳ và a là một số nguyên tố cùng nhau với n, thì

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

với φ(n) là hàm phi Euler, đếm số lượng số nguyên từ 1 đến n mà nguyên tố cùng nhau với n. Đây là một sự mở rộng của định lý nhỏ Fermat, vì khi n = p là số nguyên tố, φ(p) = p − 1.

Định lý này hữu ích để đơn giản hóa phép toán với các module n lớn. Ví dụ, có thể sử dụng để tìm chữ số tận cùng của số 7.

7 ≡ 7 ≡ (7)x7 ≡ 1x7 ≡ 49 ≡ 9 (mod 10). Do đó, chữ số tận cùng của 7 là 9.

Định lý Euler là nền tảng cho hệ thống mã hóa RSA, nhưng chỉ dựa vào định lý này không đủ để đảm bảo sự chính xác của RSA. Trong RSA, khi mã hóa và giải mã một tin nhắn văn bản, số mũ của số đầu vào lớn hơn là , đối với số nguyên dương $k$. Nếu số ban đầu là số nguyên tố tương đối với $n$, thì định lý Euler đảm bảo rằng kết quả giải mã chính là số đầu vào ban đầu, khôi phục văn bản gốc. Tuy nhiên, vì $n$ là tích của hai số nguyên tố khác nhau, $p$ và $q$, khi số mã hóa là bội số của $p$ hoặc $q$, định lý Euler không còn hiệu lực và phải dùng định lý phần dư Trung Quốc. Định lý phần dư Trung Quốc đủ điều kiện cho số tương đối nguyên tố với $n$, và do đó định lý Euler không còn cần thiết.

Chứng minh

Xét các số nguyên dương nhỏ hơn $n$ và nguyên tố cùng nhau với $n$. Với mọi cặp số phân biệt : $(a_i,n)=(a_j,n)=1\Rightarrow <!--\; \Rightarrow \; -->(a{a}_i,n)=(a{a}_j,n)=1$. Kết quả là là số dư của các số nguyên tố cùng nhau với $n$. Khi đó . Từ đó, định lý Euler được chứng minh.

Do đó, ta có .

Rút gọn đồng dư thức, .

Đã hoàn tất việc chứng minh định lý.