Định lý Euler và ung dụng

Định lý Euler & ứng dụng

1.- Phát biểu Định lý Euler
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. (Xem thêm bài “nguyên tố cùng nhau”)
Đâ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.
(Xem thêm bài “định lý nhỏ Fermat”)
2.- Chứng minh
Gọi
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
:
. Do vậy,
là một hoán vị theo mô-đun n của
.
Suy ra
.
Giản ước đồng dư thức,
.
Định lý được chứng minh.
3.- ứng dụng
Đị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.


Nguồn : Bách khoa toàn thư mở Wikipedia