Đị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ì

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 là các số nguyên dương nhỏ hơn và nguyên tố cùng nhau với . Với mọi 2 số phân biệt : . Do vậy, là một hoán vị theo mô-đun của .

Suy ra .

Giản ước đồng dư thức, .

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

Tham khảo[sửa | sửa mã nguồn]