Định lý Euler

Định lý Euler phát biểu rằng nếu n (n thuộc N*) là số nguyên dương bất kỳ và a là số nguyên tố cùng nhau với n, thì

$a^{\varphi (n)}\equiv 1{\pmod {n}}$

trong đó φ(n) là ký hiệu của phi hàm Euler đếm số các số nguyên giữa 1 và n nguyên tố cùng nhau với n. Đây là tổng quát hóa của định lý nhỏ Fermat vì nếu n = p là số nguyên tố thì φ(p) = p − 1.

Định lý này có thể được sử dụng để dễ dàng giản ước với module n rất lớn. Ví dụ tìm chữ số tận cùng của số 7²²².

7²²² ≡ 7^{4x55 + 2} ≡ (7⁴)⁵⁵x7² ≡ 1⁵⁵x7² ≡ 49 ≡ 9 (mod 10). Vậy 7²²² có chữ số tận cùng là 9.

Định lý Euler cũng là định lý cơ bản của các hệ thống mã hóa RSA tuy nhiên, việc sử dụng định lý Euler là không đủ (và không cần thiết) để chứng nhận tính hợp lệ của mã hóa RSA. Trong RSA, kết quả ròng của lần đầu tiên mã hóa tin nhắn văn bản gốc, sau đó giải mã nó, sẽ tăng số mũ của một số đầu vào lớn bằng $k\varphi (n)+1$, đối với một số nguyên dương $k$. Trong trường hợp số ban đầu tương đối nguyên tố với $n$, định lý Euler sẽ đảm bảo rằng số đầu ra được giải mã bằng với số đầu vào ban đầu, trả lại bản văn bản gốc. Tuy nhiên, vì $n$ là sản phẩm của hai số nguyên tố riêng biệt, $p$ và $q$, khi số được mã hóa là bội số của $p$ hoặc $q$, Định lý Euler không áp dụng và cần sử dụng quy định duy nhất của Định lý phần dư Trung Quốc. Định lý phần dư Trung Quốc cũng đủ trong trường hợp số tương đối nguyên tố với $n$, và do đó định lý Euler không đủ và cũng không cần thiết.

Chứng minh

Gọi $a_{1},a_{2},\cdots ,a_{\varphi (n)}$ là 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 2 số phân biệt $i,j\in \{1,2,\cdots ,\varphi (n)\}$: $(a_{i},n)=(a_{j},n)=1\Rightarrow (aa_{i},n)=(aa_{j},n)=1;aa_{i}\not \equiv aa_{j}{\pmod {n}}$. Do vậy, $aa_{1},aa_{2},\cdots ,aa_{\varphi (n)}$ là một hoán vị theo mô-đun $n$ của $a_{1},a_{2},\cdots ,a_{\varphi (n)}$.

Suy ra $a_{1}a_{2}\cdots a_{\varphi (n)}\equiv (aa_{1})(aa_{2})\cdots (aa_{\varphi (n)})\equiv a^{\varphi (n)}a_{1}a_{2}\cdots a_{\varphi (n)}{\pmod {n}}$.

Giản ước đồng dư thức, $a^{\varphi (n)}\equiv 1{\pmod {n}}$.

Định lý đã được chứng minh