Sáng kiến kinh nghiệm Định lí euler và tính ứng dụng thực tiễn

ơng để p
∣∣∣ 2n2+1− 3n, hay
2n
2+1 ≡ 3n (mod p).
Vì n2 + 1 và n khác tính chẵn lẻ, nên từ đây suy ra 2 hoặc 3 phải là số chính
phương mod p (vô lí). Vậy,P \ A chứa tất cả số nguyên tố dạng 24k+ 5. Theo
định lí Dirichlet thì tập này là tập vô hạn.
Để chứng minh A là tập vô hạn, ta giả sử phản chứng A có hữu hạn phần
tử, đặt M = p1p2 · · · pm là tích tất cả các phần tử của A. Rõ ràng 2 /∈ A nên
mọi pi đều lẻ.
Xét n = ϕ(M) = (p1− 1) · · · (pm − 1) thì
2n
2+1− 3n = 2[(p1−1)···(pm−1)]2+1− 3(p1−1)···(pm−1)
≡ 2 (mod pi), ∀i = 1, 2, · · · ,m.
Suy ra 2n
2+1− 3n không chia hết cho bất cứ số nguyên tố nào thuộc A, nên tồn
tại ước nguyên tố của số này thuộc Amà không trùng với pi (i = 1, 2, · · · ,m),
vô lí. Từ đó ta có điều cần chứng minh.
2.3. Ứng dụng vào hệ mã hóa RSA
Định lí Euler không chỉ là một định lí quan trọng bậc nhất trong Số học,
mà còn có rất nhiều tính ứng dụng thực tiễn vào Khoa học, đặc biệt là ứng
dụng vào Mật mã học với hệ mã hóa RSA. Dưới đây ta sẽ đi tìm hiểu nguyên
lí của hệ mã hóa RSA cũng như ứng dụng thực tế của nó.
26
2.3.1. Nguyên lí của hệ mã hóa RSA
Một quá trình của hệ mã hóa RSA bắt đầu với việc người nhận gửi cho
người khởi tạo hai số nguyên. Hai số nguyên đó được chọn như sau:
Đầu tiên, anh ta lấy 2 số nguyên tố p và q. Sau đó, anh ấy tính n = pq, và
ϕ(n) = ϕ(p)ϕ(q) = (p− 1)(q− 1).
Cuối cùng, anh ấy chọn số nguyên e sao cho 1 < e < ϕ(n) và gcd(e, ϕ(n)) =
1. Lí do phải chọn e để gcd(e, ϕ(n)) = 1 là để chắc chắn tồn tại d = e−1
(mod ϕ(n)).
Sau đó, người nhận chỉ gửi giá trị của e và n cho người khởi tạo. Những
giá trị này được công khai, còn giá trị của p và q được giữ bí mật.
Sau khi người khởi tạo nhận 2 giá trị e và n, anh ta có các thông tin cần
thiết để mã hóa tin nhắn anh ấy dự kiến gửi cho người nhận thông qua các
kênh chưa đảm bảo an ninh. Chìa khóa mã hóa công khai là e, còn hàm mã
hóa là y ≡ xe (mod n), trong đó y là số nguyên tương ứng với bản mã, và x
là số nguyên tương ứng với văn bản gốc. Người khởi tạo sau đó có thể gửi
các đoạn tin nhắn đã mã hóa cho người nhận.
Khi người nhận nhận được bản mã hóa, anh này trước hết sẽ tìm d để
d = e−1 (mod ϕ(n)). Số d này là chìa khóa giải mã cá nhân . Hàm giải mã
lúc này là x ≡ yd (mod n).
American Standard Code for Information Integerchange (viết tắt là ASCII)
là một danh sách các số từ 32 đến 126 và kí tự tương ứng của chúng, dùng
trong hệ mã hóa RSA, được cho ở bảng dưới đây
27
2.3.2. Ví dụ thực tế
Ví dụ 3. Giả sử Việt là người nhận, còn Nam là người khởi tạo. Việt đang làm
việc cho quân đội Việt Nam, còn Nam đang làm gián điệp ở một đất nước
khác. Nam nghe ngóng được một cuộc tấn công vào Việt Nam và muốn gửi
một tin nhắn đặc biệt tối mật cho Việt với nội dung là "now" (ngay bây giờ).
Việt sẽ bắt đầu bằng việc chọn 2 số nguyên tố, p = 13 và q = 29. Anh tìm
ra n = 377 và ϕ(n) = (p− 1)(q− 1) = 336.
Anh ấy tiếp tục chọn e = 11 để thỏa mãn 1 < e < 336 và gcd(e, 336) = 1.
Anh ấy gửi 2 số 11 và 377 cho Nam thông qua 1 kênh thông tin không đảm
bảo an ninh (và có thể là công khai).
Nam nhận các số trên, và bắt đầu mã hóa, sử dụng chìa khóa mã hóa
28
công khai 11 và hàm mã hóa y ≡ x11 (mod 377). Vì Nam muốn mã hóa
tin nhắn "now" (ngay bây giờ), sử dụng bảng ASCII, văn bản gốc lúc này là
110, 111, 119. Anh ấy bắt đầu quá trình mã hóa:
y ≡ 11011 ≡ 310 (mod 377)
y ≡ 11111 ≡ 132 (mod 377)
y ≡ 11911 ≡ 189 (mod 377)
Nam sau đó gửi các bản mã hóa, 310, 132, 189 tới Việt. Lúc này, để giải mã
tin nhắn này, Việt đầu tiên phải tìm d để 11d ≡ 1 (mod 336). Chìa khóa giải
mã cá nhân d lúc này là 275, vì 11 · 275 ≡ 1 (mod 336). Việt lúc này có thể
bắt đầu quá trình giải mã như sau
x ≡ 310275 ≡ 110 (mod 377)
y ≡ 132275 ≡ 111 (mod 377)
y ≡ 189275 ≡ 119 (mod 377)
Đối chiếu với bảng ASCII, Việt lúc này có thể khám phá tin nhắn gốc từ Nam
là: "now".
Giải thích. Tiếp theo, ta sẽ lí giải vì sao người nhận có thể giải mã bản mã
hóa e, sử dụng chìa khóa d để nhận được tin nhắn gốc M.
Gọi M là văn bản gốc mà người khởi tạo sẽ mã hóa và gửi cho người
nhận. Gọi e là chìa khóa mã hóa công khai, d là chìa khóa giải mã cá nhân,
c là bản mã hóa, n = pq và ϕ(n) = (p− 1)(q− 1). Người khởi tạo mã hóa
M bằng cách tính c ≡ Me (mod n) và gửi giá trị c cho người nhận. Sau đó,
người nhận chuyển c thành văn bản gốc bằng cách tìm đồng dư của cd theo
mod n. Ta sẽ chứng minh cd ≡ M (mod n), có nghĩa là cd theo mod n sẽ trả
lại giá trị M ban đầu.
Thật vậy, để ý cd ≡ (Me)d (mod n). Người nhận biết rằng
ed ≡ 1 (mod ϕ(n)),
khi đó
cd ≡ Med ≡ M
(
Mϕ(n)
)k
(mod n),
với k nguyên dương nào đó. Khi đó, theo định lí Euler, vì gcd(M, n) = 1 nên
Mϕ(n) ≡ 1 (mod n). Vì vậy, cd ≡ M (mod n).
29
Ví dụ sau đây mô tả sự bảo mật của hệ mã hóa RSA.
Ví dụ 4. Giả sử có 3 nhân viên chia sẻ các giá trị e và n của họ cho nhau như
sau:
An Bình Chi
(11, 35) (23, 247) (31, 187)
Giả sử Bình muốn gửi cho An một tin nhắn đã mã hóa, anh ấy phải sử
dụng các số của An. Do đó, anh ấy phải gửi cho An số M11 (mod 35), trong
đó M là văn bản gốc định gửi.
An sau đó giải mã tin nhắn từ Bình bằng cách sử dụng giá trị ϕ(n) bí mật
của cô ấy và tính giá trị d. Tức là, Chi sẽ không thể giải mã tin nhắn đó vì cô
ấy không biết giá trị ϕ(n) của An.
Mặt khác, Chi cũng không biết giá trị n của An phân tích thành 2 số
nguyên tố như thế nào (áp dụng với các số nguyên tố rất lớn và do đó, giá trị
n rất lớn).
Hơn nữa, nếu Chi mã hóa 1 tin nhắn gửi cho Bình mà sử dụng chìa khóa
mã hóa công khai của An, Bình cũng sẽ không thể giải mã được.
Cuối cùng, trong khi các giá trị sử dụng trong quá trình mã hóa được
công khai hoàn toàn, thì sự xác định chìa khóa khóa giải mã của một người
nào đó từ chìa khóa mã hóa của họ là không thể thực hiện được trong các
trường hợp chính xác của hệ thống mật mã.
2.4. Bài tập tự luyện
Bài toán 20. Chỉ ra ít nhất 2 nghiệm của hệ phương trình đồng dưx29+ y11 ≡ 1 (mod 210)x, y 6≡ 0 (mod 210) .
Bài toán 21. Chứng minh rằng các phương trình đồng dư sau có nghiệm
(x; y; z; t) khác (0; 0; 0; 0):
a) x3+ y3+ z3 ≡ t3 (mod 210).
30
b) x5+ y5+ z5 ≡ t5 (mod 1155).
Bài toán 22. Tìm ít nhất một nghiệm của phương trình đồng dư sau:
x11+ y13 ≡ 1 (mod45).
Bài toán 23. Chứng tỏ rằng mỗi phương trình sau có nghiệm nguyên dương.
a) 2x + 3y + 5z + 7t ≡ 3(mod210).
b) 3x + 5y + 7z ≡ 2(mod105).
Bài toán 24. Cho số nguyên dương n và số nguyên m ≥ 2 thỏa mãn phương
trình đồng dư
xm ≡ a (mod n)
có nghiệm với mọi a nguyên. Chứng minh rằng phân tích tiêu chuẩn của n
có dạng n = p1p2 · · · pk, và gcd(r, pi) = 1, ∀i = 1, k.
Bài toán 25. Chứng minh rằng với mọi m, n nguyên dương, tồn tại a nguyên
dương để ϕ(a), ϕ(a+ 1), · · · , ϕ(a+ n) đều chia hết cho m.
Bài toán 26. Cho p là một số nguyên tố, n là số nguyên dương bất kì thỏa
mãn 1 < n < p. Chứng minh rằng:
p
∣∣∣ ϕ (1+ n+ n2+ · · ·+ np−1) .
Bài toán 27. Cho a1, a2, · · · , an là các số hữu tỉ thỏa mãn ak1 + ak2 + · · · + akn
là số nguyên với mọi k nguyên dương. Chứng minh a1, a2, · · · , an là các số
nguyên dương.
Bài toán 28. Cho trước một số x nguyên dương. Chứng minh rằng tồn tại vô
hạn số nguyên tố p có dạng 4k + 3, sao cho p | 2nx + 1, với n là số nguyên
dương nào đó.
Bài toán 29. Chứng minh rằng với mọi số nguyên dương a, b cho trước, tồn
tại vô hạn n nguyên dương để a
∣∣∣ bn − n.
Bài toán 30. Chứng minh rằng tồn tại vô hạn số nguyên dương n thỏa mãn
tính chất: ta có thể đổi chỗ 2 chữ số phân biệt khác 0 của n mà không làm
thay đổi tập ước nguyên tố của nó.
31
Bài toán 31. Cho a, b là hai số hữu tỉ dương phân biệt thỏa mãn an − bn là số
nguyên với vô hạn giá trị n nguyên dương. Chứng minh a, b là số nguyên.
Bài toán 32. Cho a > b là hai số nguyên dương thỏa mãn S(an) = S(bn)
với mọi n nguyên dương (ở đây S(x) là tổng tất cả các chữ số của số nguyên
dương x). Chứng minh rằng
a
b
là một lũy thừa của 10.
Bài toán 33. Cho p = 3181, q = 227 và e = 953. Mã hóa văn bản gốc sau: "161
MAIN STREET". Sau đó, tìm chìa khóa giải mã d và giải mã bản mã hóa.
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.
Qua thực tế giảng dạy cho các em học sinh lớp chuyên Toán và bồi dưỡng
các em trong đội tuyển thi HSG quốc gia của tỉnh Nghệ An, tôi thấy các em
rất thích thú khi được học nội dung kiến thức này.
Việc phân loại một số dạng toán số học dùng Định lí Euler sẽ giúp cho
các em học sinh thấy được sự ứng dụng đa dạng của nội dung lí thuyết, điều
này khích lệ phong trào học tập của học sinh đặc biệt là những học sinh có
tố chất toán học cao, có khả năng tham gia các kì thi toán Olympic Quốc gia
và Quốc tế.
Trước khi áp dụng sáng kiến kinh nghiệm này: các em học sinh ở khối 10
chuyên Toán, khi chưa được học về định lí Euler thì phân tích và tìm lời giải
không được ngắn gọn và sắc bén. Nhưng nếu các em được học về nội dung
định lí và các tính chất hệ quả, cùng với tư duy theo hướng này thì việc tiếp
cận đến lời giải sẽ dễ dàng hơn và trình bày ngắn ngọn hơn.
Sau khi áp dụng sáng kiến: các em sẽ có thêm cơ sở lí luận để tìm tòi lời
giải những bài toán liên quan đến phương trình đồng, chứng minh tồn tại...
như các bài 1, 7, 15, v,v,.. hầu hết các em trong đội tuyển quốc gia đều làm
được khi biết sử dung kiến thức này.
Sáng kiến kinh nghiệm cũng đã được giảng dạy cho các em trong đội
tuyển tham dự kì thi HSG quốc gia năm học 2022 – 2023, đội tuyển đã giành
được 3 giải nhì, 4 giải ba, và 3 giải khuyến khích. Trong đó có hai em được
tham dự kì thi chọn Đội tuyển tham dự kì thi Olympic Toán quốc tế năm
32
2023. Trong sáng kiến kinh nghiệm này cũng đã đưa ra một hệ thống bài tập
cho học sinh để rèn luyện, cũng cố phương pháp.
Nội dung sáng kiến kinh nghiệm cũng đã được báo cáo trực tuyến tại
“Cuộc thi bài viết và bài giảng Hoàng Tụy lần thứ nhất năm 2022”, đề tài
được các đồng nghiệp đánh giá cao (dành giải 3 trong số hơn 600 bài viết dự
thi) và xem đây là một tài liệu quan trọng trong giảng dạy và bồi dưỡng học
sinh giỏi về Số học.
33
Chương 3
KẾT LUẬN
3.1. Kết luận
Bài viết này trình bày các vấn đề cơ bản về định lí Euler và những áp dụng
của nó vào một số bài toán hay và khó trong các bài thi Olympic. Bài viết đã
được giảng dạy cho các em học sinh chuyên toán thi HSGQG và thi chọn đội
tuyển Olympic quốc tế. Qua thực tế giảng dạy các em học sinh tiếp thu rất
tốt và kết quả các em đều vận dụng được khi gặp dạng toán liên quan. Tác
giả hy vọng rằng bài viết này sẽ là một tài liệu tham khảo bổ ích cho các thầy,
cô và các em học sinh chuyên toán. Tác giả rất mong nhận được những góp
ý quý báu từ các thầy, cô để chuyên đề được hoàn thiện sâu sắc hơn nữa. Xin
chân thành cám ơn.
3.2. Kiến nghị và đề xuất
Qua việc thực hiện đề tài: “Định lí Euler và tính ứng dụng thực tiễn”, tôi
rút ra một số kiến nghị sau:
• Đối với học sinh: Các em cần học và nắm chắc kiến thức xuyên suốt từ
các cấp dưới. Từ đó tạo nền tảng Số học tốt để tiếp nối lên cấp THPT và
xa hơn chính là thi HSG các cấp. Cần tự làm bài dưới sự hướng dẫn của
giáo viên và chủ động tìm tòi, làm thêm các dạng bài tương tự trên các
phương tiện mạng hiện nay.
• Đối với giáo viên: Giáo viên cần nâng cao chuyên môn nghiệp vụ bằng
34
cách tự nghiên cứu, cập nhật và đào sâu vào các chuyên đề Toán chuyên.
Cần động viên học sinh làm tốt nhiệm vụ mà giáo viên giao để khuyến
khích các em phát huy sự quyết tâm, tạo niềm say mê với môn học.
• Đối với tổ chuyên môn: Trong sinh hoạt tổ chuyênmôn nên dành thời gian
trao đổi kinh nghiệm, xây dựng hệ thống các chuyên đề Toán chuyên để
phục vụ cho mục tiêu bồi dưỡng HSG các cấp.
• Đối với nhà trường: thường xuyên tổ chức các lớp bồi dưỡng chuyên môn
cho giáo viên và các buổi trao đổi học hỏi kinh nghiệm với các đơn vị
khác trong khu vực.
35
Tài liệu tham khảo
[1] Titu Andreescu & Dorin Adrica, "Number Theory Structures, Examples
and Problems". (2009)
[2] Titu Andreescu, Gabriel Dospinescu, Oleg Mushkarov, "Number The-
ory: Concepts and Problems", XYZ Press. (2017)
[3] Nhiều tác giả, "Chuyên đề Số học VMF". (2012)
[4] Titu Andreescu & Gabriel Dospinescu, "Problem from the Book" . (2010)
[5]
[6]
36
PHỤ LỤC
KHẢO SÁT SỰ CẤP THIẾT VÀ TÍNH
KHẢ THI CỦA CÁC GIẢI PHÁP ĐỀ
XUẤT
1. Mục đích khảo sát
Để hoàn tất sáng kiến kinh nghiệm, tôi đã tạo google form và có nhờ các
em học sinh trong đội tuyển HSG Quốc Gia và các em học sinh khác, cũng
như các thầy cô giáo tham gia khảo sát bằng google form. Mục đích là để
đánh giá một cách khách quan hơn về sự cấp thiết và tính khả thi của các
giải pháp đề xuất đối với đề tài nghiên cứu. Qua đó cũng là để tiếp thu và
có sự điều chỉnh cần thiết để hoàn thiện đề tài hiện tại, cũng như các đề tài
khác trong thời gian tới.
2. Nội dung và phương pháp khảo sát
2.1 Nội dung khảo sát
Nội dung khảo sát tập trung vào 02 vấn đề chính sau:
1) Các giải pháp được đề xuất có thực sự cấp thiết đối với vấn đề định lí
Euler và tính ứng dụng thực tiễn không?
2) Các giải pháp được đề xuất có khả thi đối với vấn đề định lí Euler và
tính ứng dụng thực tiễn không?
37
2.2 Phương pháp khảo sát và thang đánh giá
Phương pháp được sử dụng để khảo sát là khảo sát bằng google form; với
thang đánh giá 04 mức (tương ứng với điểm số từ 1 đến 4):
• Sự cấp thiết: Không cấp thiết; Ít cấp thiết; Cấp thiết; Rất cấp thiết.
• Tính khả thi: Không khả thi; Ít khả thi; Khả thi; Rất khả thi.
3. Đối tượng khảo sát
STT Đối tượng Số lượng
1 Học sinh (Chuyên Toán) 15
2 Học sinh (Không chuyên) 9
3 Giáo viên 11
∑ 35
4. Kết quả khảo sát về sự cấp thiết và tính khả thi của các
giải pháp đã đề xuất
4.1 Sự cấp thiết của các giải pháp đã đề xuất
Đánh giá sự cấp thiết của các giải pháp đề xuất
STT Các giải pháp
Các thông số
X Mức
1 Đối với học sinh 3, 08 Cấp thiết
2 Đối với giáo viên 3, 22 Cấp thiết
3 Đối với tổ chuyên môn 4 Rất cấp thiết
4 Đối với nhà trường 4 Rất cấp thiết
Từ số liệu thu được ở bảng trên có thể rút ra những nhận xét:
• Các giải pháp đối với học sinh và giáo viên mang tính cấp thiết. Việc
tự tìm tòi, nghiên cứu và nâng cao chuyên môn nghiệp vụ (ở giáo viên)
38
và việc chủ động tìm và làm các bài tập trên các phương tiện mạng rất
được hưởng ứng và là xu thế hiện nay.
• Các giải pháp đối với tổ chuyên môn và nhà trường là thực sự cấp thiết.
Nhà trường cũng muốn tạo điều kiện để các giáo viên dạy chuyên có cơ
hội tập huấn, trau dồi chuyên môn và học hỏi kinh nghiệm.
4.2 Tính khả thi của các giải pháp đã đề xuất
Đánh giá tính khả thi của các giải pháp đề xuất
STT Các giải pháp
Các thông số
X Mức
1 Đối với học sinh 3, 21 Khả thi
2 Đối với giáo viên 3, 33 Khả thi
3 Đối với tổ chuyên môn 3 Khả thi
4 Đối với nhà trường 4 Rất khả thi
Từ số liệu thu được ở bảng trên có thể rút ra những nhận xét:
• Các giải pháp đối với học sinh và giáo viên và tổ chuyênmôn có tính khả
thi. Điều này thể hiện sự nhất trí của học sinh, giáo viên và tổ chuyên
môn đối với đề xuất trong đề tài nghiên cứu.
• Các giải pháp đối với nhà trường rất khả thi và được sự ủng hộ cao từ
ban giám hiệu nhà trường.
39