Ktl-icon-tai-lieu

Định lý Euler

Được đăng lên bởi Phan Đình Phong
Số trang: 1 trang   |   Lượt xem: 344 lần   |   Lượt tải: 1 lần
Đị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ửasử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
:
vậy,

. Do
là một hoán vị theo mô-đun

Suy ra
Giản ước đồng dư thức,
Định lý được chứng minh.

của

.
.

.

...
Đị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ố 7
222
.
7
222
≡ 7
4x55 + 2
≡ (7
4
)
55
x7
2
≡ 1
55
x7
2
≡ 49 ≡ 9 (mod 10). Vậy 7
222
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ửasử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.
Định lý Euler - Người đăng: Phan Đình Phong
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
1 Vietnamese
Định lý Euler 9 10 471