SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN
TRƯỜNG THPT CHUYÊN PHAN BỘI CHÂU
SÁNG KIẾN KINH NGHIỆM
Đề tài:
ĐỊNH LÍ EULER VÀ TÍNH ỨNG DỤNG THỰC TIỄN
LĨNH VỰC: TOÁN HỌC
Tác giả: Phan Phương Đức
Tổ bộ môn: Toán - Tin
Năm học: 2022-2023
Mục lục
Chương1.ĐẶTVẤNĐỀ............................................. 5
1.1.Lýdochọnđềtài............................................... 5
1.2.Mụcđíchnghiêncứu........................................... 6
1.3.Phạmvinghiêncứu............................................. 6
1.4.Nhiệmvụnghiêncứu........................................... 6
1.5.Phươngphápnghiêncứu....................................... 7
Chương2.NỘIDUNGNGHIÊNCỨU............................... 8
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm. . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.1. Phi hàm Euler. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.2. Định lí Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.3. Các tính chất và hệ quả . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2. Phân loại một số bài toán liên quan đến định lí Euler . . . . . . . . . . . 13
2.2.1. Các bài toán về nghiệm của phương trình, hệ phương trình đồng dư . . . . . . . . . . . . 13
2.2.2. Các bài toán về chứng minh sự tồn tại, không tồn tại . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3. Các bài toán về phi hàm Euler. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.4. Các bài toán khác . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.ỨngdụngvàohệmãhóaRSA................................. 26
2.3.1. Nguyên lí của hệ mã hóa RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.2. Ví dụ thực tế . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.Bàitậptựluyện................................................ 30
2.5. Hiệu quả của sáng kiến kinh nghiệm đối với hoạt động giáo dục, với
bản thân, đồng nghiệp và nhà trường.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2
Chương3.KẾTLUẬN............................................... 34
3.1.Kếtluận....................................................... 34
3.2.Kiếnnghịvàđềxuất........................................... 34
Tàiliệuthamkhảo................................................... 36
Phụlục.............................................................. 37
Các kí hiệu sử dụng trong sáng kiến kinh nghiệm
≡đồng dư
gcd ước chung lớn nhất
a
b a chia hết b(hoặc bchia hết cho a)
|A|lực lượng (số phần tử) của tập hợp A
∏tích sigma
vp(a)số mũ đúng của atheo ước pnguyên tố
a
bkí hiệu Legendre về thặng dư bình phương
∑tổng sigma
A\Bhiệu của tập Atrừ tập B
⌊x⌋phần nguyên của x
Chương 1
ĐẶT VẤN ĐỀ
1.1. Lý do chọn đề tài
Ngay từ lớp 6, khi học về lũy thừa, các học sinh khá giỏi đã được tiếp cận
dạng bài toán: tìm số dư khi chia 1 lũy thừa lớn cho một số tự nhiên A nào
đó, trong đó có bài toán tìm chữ số tận cùng, nhiều chữ số tận cùng của một
lũy thừa. Cách làm thời điểm đó về cơ bản là xét sự tuần hoàn số dư của lũy
thừa tăng dần theo cơ số đó khi chia cho A. Sau khi học thêm về số nguyên
tố, học sinh khá giỏi cấp THCS và theo định hướng chuyên toán có thể được
học thêm định lí Fermat nhỏ, là 1 định lí tốt để không chỉ dùng cho việc xác
định số dư như đề cập ở trên, mà còn để giải quyết các bài toán Số học về số
nguyên tố.
Trong bài viết này, tôi xin trình bày về Định lí Euler, là định lí tổng quát
cho định lí Fermat nhỏ, là một công cụ sắc bén giải quyết nhiều bài toán Số
học, hay và khó trong các kì thi Olympic trên toàn thế giới. Do khuôn khổ
bài viết bị giới hạn về số trang, nên tôi sẽ trình bày vấn đề lí thuyết một cách
cơ bản (với mục đích được phổ biến rộng rãi đến bạn đọc) và một số ví dụ áp
dụng minh họa trong các đề thi Olympic, để thấy được sự sắc bén của vấn
đề này.
Ngoài ra, tôi còn trình bày về tính ứng dụng thực tiễn của định lí Euler,
chính là hệ mã hóa RSA, một trong những hệ mã hóa có tính bảo mật và ứng
dụng rất cao hiện nay.
5
