Định lý Euler

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Đị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ố 7222.

7222 ≡ 74x55 + 2 ≡ (74)55x72 ≡ 155x72 ≡ 49 ≡ 9 (mod 10). Vậy 7222 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[sửa | sửa mã nguồn]

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_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.