Định lý Euler

Định lý Euler phát biểu rằng nếu 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 mô-đun 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.

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,m)=(a,m)=1 \Rightarrow (aa_i,m)=(aa_i,m)=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_1a_2\cdots a_{\varphi (n)}\equiv (aa_1)(aa_2)\cdots (a_{\varphi (n)}) \equiv a^{\varphi (n)}a_1a_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.