SKKN Định lí EULER và tính ứng dụng thực tiễn

ĐẶ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
1.2. Mục đích nghiên cứu
Trên cơ sở nghiên cứu những vấn đề cơ bản của định lí Euler và các tính chất hệ quả, sáng kiến xác định các biện pháp bồi dưỡng năng lực học Số học cho học sinh nhằm phát triển tư duy nghiên cứu chuyên sâu cho học sinh chuyên Toán.
Rèn luyện kĩ năng vận dụng định lí Euler và các hệ quả vào giải toán thông qua các bài thi học sinh giỏi và các kì thi Olympic. Hướng cho học sinh đến việc hiểu được tính ứng dụng thực tiễn của định lí nói riêng, và của Toán học nói chung trong dòng chảy cuộc sống hiện đại, giúp cho các em có định hướng tốt hơn cho môn học.
1.3. Phạm vi nghiên cứu
Dựa trên dữ liệu các đề thi học sinh giỏi, kì thi Olympic trong nước và nước ngoài, đề tài tập trung nghiên cứu và đề xuất các bài toán rèn luyện tư duy sáng tạo cho học sinh chuyên Toán và học sinh tham gia các đội tuyển thi học sinh giỏi các cấp.
1.4. Nhiệm vụ nghiên cứu
Đề tài tập trung làm rõ một số vấn đề sau:
• Khái niệm phi hàm Euler và phát biểu định lí Euler.
• Các tính chất và hệ quả của định lí.
• Các bài toán áp dụng.
• Ứng dụng vào hệ mã hóa RSA.
• 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.
6

1.5. Phương pháp nghiên cứu
Tham khảo tài liệu trong và ngoài nước về Số học để biên soạn cơ sở lí thuyết về định lí Euler. Phân loại một số dạng đề thi Olympic toán được giải bằng định lí Euler. Nếu học sinh được học chuyên sâu theo chuyên đề sẽ phát triển năng lực tư duy Toán học, đặc biệt là có phương pháp để giải quyết được một lớp các bài toán về số học liên quan đến định lí Euler. Đây là phần khó với học sinh các lớp chuyên toán.
Tham khảo các nguồn tài liệu, sách báo trong và ngoài nước để biên soạn tính ứng dụng của định lí vào hệ mã hóa RSA.
7

Chương 2
NỘI DUNG NGHIÊN CỨU
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm
2.1.1. Phi hàm Euler
Trước hết, ta định nghĩa phi hàm Euler của một số nguyên dương n.
Định nghĩa 2.1.1. Với mỗi số nguyên dương n, kí hiệu φ(n) là số các số nguyên dương nhỏ hơn n và nguyên tố cùng nhau với n. Ta gọi φ(n) là phi hàm Euler của n.
Quy ước. φ(1) = 1.
Ví dụ.
• φ(3)=2,vìcó2sốnguyêndươngnhỏhơn3vànguyêntốcùngnhau với 3 (là các số 1, 2).
• φ(12) = 4, vì có 4 số nguyên dương nhỏ hơn 12 và nguyên tố cùng nhau với 12 (là các số 1,5,7,11).
Nhận xét. Rõ ràng nếu p là số nguyên tố thì φ(p) = p − 1. 2.1.2. Định lí Euler
Với số nguyên dương n, có duy nhất 1 số φ(n) tương ứng. Vậy hằng số này có ứng dụng gì? Ta có nội dung định lí Euler, là phát biểu chính của cơ sở lí thuyết như sau:
8

Định lí 2.1.2. (Định lí Euler) Cho n là một số nguyên dương bất kì. Khi đó, nếu a là số nguyên dương nguyên tố cùng nhau với n, ta luôn có
aφ(n) ≡ 1 (mod n).
Chứng minh. Gọi a1, a2, · · · , aφ(n) là các số nguyên dương nhỏ hơn n và nguyên tố cùng nhau với n. Theo định nghĩa hệ thặng dư thu gọn (HTDTG) thì các số trên lập thành 1 HTDTG modn.
Với a ∈ Z+, (a, n) = 1 bất kì, theo tính chất của HTDTG thì bộ
aa ,aa ,··· ,aa  12 φ(n)
cũng lập thành 1 HTDTG modn. Khi đó ta thu được
a1a2 ···aφ(n) ≡ aa1 ·aa2 ···aaφ(n) = aφ(n)a1a2 ···aφ(n) (mod n).
Vì a1,a2,··· ,aφ(n) là các số nguyên dương nhỏ hơn n và nguyên tố cùng
nhau với n nên từ đó suy ra
aφ(n) ≡ 1 (mod n).
Hệ quả 2.1.3. (Định lí Fermat nhỏ) Với mỗi p nguyên tố thì
ap−1 ≡1 (mod p),∀a∈Z+,gcd(a,p)=1.
Chứng minh. Với p nguyên tố thì tất cả các số nguyên dương nhỏ hơn p đều nguyên tố cùng nhau với p. Do đó φ(p) = p − 1. Áp dụng định lí Euler ta có điều cần chứng minh.
Ví dụ 1. Tìm số dư khi chia 29112021 cho 12.
Phân tích. Như đã nói ở đầu, đây là dạng bài toán mà ta phải đi tìm hằng số a sao cho 29a đồng dư 1 hoặc −1 theo mod 12. Định lí Euler cho ta số a thỏa mãn điều kiện này.
Chứng minh. Ta có φ(12) = 4. Hơn nữa, vì (29, 12) = 1 nên áp dụng định lí Euler, ta có
294 ≡ 1 (mod 12).
9

Dễthấy112021 ≡3 (mod4),nên112021 =4k+3.Dođó, 29112021 = 294k+3 = 294k · 293
≡293 ≡53 ≡5 (mod12). Vậy, 29112021 chia 12 được dư là 5.
Chúý.a=4khôngphảilàsốnguyêndươngnhỏnhấtthỏamãn29a ≡1 (mod 12), vì
292 ≡52 ≡1 (mod12). 2.1.3. Các tính chất và hệ quả
Đôi khi để sử dụng định lí Euler, ta cần biết công thức để tính phi hàm Euler φ(n), đặc biệt khi n là một số khá lớn. Ta có các tính chất sau để suy ra công thức tính phi hàm Euler cho một số n bất kì.
Tính chất 2.1.4.
k k−1 +
φ p =p (p−1),∀p∈P,k∈Z . (2.1)
Phântích. Đểýlàgcdn,pk>1⇔gcd(n,p)>1⇔p n. Dođó,thayvìđếmsốcácsốnnhỏhơnpk vànguyêntốcùngnhauvớipk,ta cóthểđếmsốcácsốnnhỏhơnpk vàlàbộicủap.
Chứng minh. Từ 1 đến pk, các số là bội của p có thể lập thành dãy: p, 2p, · · · pk−1 · p,
nên có pk−1 số như vậy. Các số nguyên dương còn lại nhỏ hơn pk đều nguyên tố cùng nhau với pk. Vì vậy,
k k k−1 k−1
φp =p−p =p (p−1).
Tính chất 2.1.5. φ(mn) = φ(m) · φ(n), nếu gcd(m, n) = 1. Với tính chất này thì φ(n) là một hàm nhân tính số học.
10

Chứng minh. Gọi A, B, C lần lượt là tập hợp các số nguyên dương nguyên tố cùng nhau và nhỏ hơn m, n, mn. Khi đó,
φ(m) = |A|, φ(n) = |B|, φ(mn) = |C|.
Hơn nữa, với mỗi a ∈ A, b ∈ B, vì gcd(m, n) = 1 nên theo định lí phần dư
Trung Hoa, tồn tại duy nhất một số c ∈ C thỏa mãn hệ đồng dư:c≡a (modm)
.
c≡b (modn)
Do đó, ta có một song ánh từ A × B vào C, dẫn đến |A| · |B| = |C|, tức là
φ(mn) = φ(m) · φ(n).
Từ 2 tính chất trên, ta thu được cách tính φ(n) của 1 số n bất kì như sau. Tínhchất2.1.6.Nếuphântíchtiêuchuẩncủanlàn=pα1pα2···pαk thì
12k 111
φ(n)=n 1−p 1−p ··· 1−p , (2.2) 12k
Chứngminh. Thật vậy, với n = pα1pα2 ···pαk, áp dụng 2 tính chất 2.1.4 và 12n
2.1.5, ta có:
φ(n) = φ pα1
φ pα1
· · · φ pαk

12k
= pα1−1(p1 − 1)pα2−1(p2 − 1) · · · pαk−1(pk − 1) 12k
111 =n1−p1−p···1−p.
12k
Tính chất tiếp theo có vai trò quan trọng trong việc ứng dụng định lí Euler vào các bài toán chỉ ra sự tồn tại nghiệm của các phương trình đồng dư.
Tính chất 2.1.7. Với a, b là 2 số nguyên dương bất kì nguyên tố cùng nhau, ta luôn có
aφ(b) + bφ(a) ≡ 1 (mod ab). (2.3) 11

Chứng minh. Vì gcd(a, b) = 1 nên theo định lí Euler thì aφ(b) ≡ 1 (mod b) và bφ(a) ≡1 (moda).Từđóaφ(b)+bφ(a)−1chiahếtchocảavàb.Tacóđiều cần chứng minh.
Hệ quả 2.1.8. Với a, b là 2 số nguyên dương bất kì nguyên tố cùng nhau, và m, n nguyên dương bất kì ta luôn có
amφ(b) + bnφ(a) ≡ 1 (mod ab). (2.4)
Tính chất 2.1.9. Giả sử có k ≥ 2 số nguyên dương m1,m2,···mk đôi một nguyêntốcùngnhau.ĐặtM=m1·m2···mk =miti vớii=1,2,3…,k,khi đó
tφ(m1)+tφ(m2)+…+tφ(mk) ≡1 (modM). 12k
Chứng minh. Từ giả thiết ta có (mi,ti) = 1 với mỗi i = 1,2,··· ,k nên theo định lí Euler thì
tφ(m1) ≡ 1 (modmi) . (2.5) 1
Mặt khác với i,j thuộc tập {1,2,··· ,k} và i ̸= j thì tj chia hết cho mj nên tj,mi
= mi hay
tφ(mi) ≡ 0 (modmi) . (2.6) j
Đặt S = tφ(m1) + tφ(m2) + . . . + tφ(mk). Từ (2.5) và (2.6) ta có 12k
S≡tφmi ≡1(modmi). i
Mà m1,m2,··· ,mk đôi một nguyên tố cùng nhau, nên suy ra tφ(m1) +tφ(m2) +…+tφ(mk) ≡ 1 (modm1 ·m2 …mk),
12k tức là điều cần chứng minh.
Hệ quả 2.1.10. Với giả thiết từ tính chất 2.1.9, ta luôn có t1n+t2n+···+tnk ≡(t1+t2+···+tk)n (modM),
với mọi n nguyên dương.
12

Ví dụ 2. Chứng minh sự tồn tại nghiệm của hệ phương trình đồng dư: 

x ≡ a (mod m )
11
x ≡ a2 (mod m2)
,
············
x ≡ ak (mod mk)
trongđóa1,a2,··· ,ak làcácsốnguyênbấtkì,m1,m2,··· ,mk làcácsốnguyên dương bất kì đôi một nguyên tố cùng nhau. (định lí phần dư Trung Hoa)
Phân tích. Ta cần tìm 1 số x có dạng x = A1 + A2 + · · · + Ak sao cho với mỗi
i ∈ 1, k thì
Ai≡0 (modmj),∀j̸=i
.
Ai ≡ ai (mod mi)
Hơn nữa, các biểu thức A1, A2, · · · , Ak phải có tính đối xứng giữa các biến m1,m2,··· ,mk. Từ đó ta nghĩ đến việc chọn các biểu thức Ai chứa tích các biến m1,m2,··· ,mk trừ mi.
Chứng minh. Ta chọn
 k φ(m1)
 ∏ mj  x = a1  j=1 
 k φ(m2)  ∏ mj 
+ a2  j=1  m2 
2.2. Phân loại một số bài toán liên quan đến định lí Euler
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ư
Bài toán 1. Chỉ ra ít nhất 2 nghiệm của phương trình đồng dư: x5+y6≡1 (mod28),
mk 
Từ đây, theo định lí Euler, dễ dàng kiểm tra được x thỏa mãn phương trình
đồng dư ban đầu.
m1  
 k φ(mk)
 ∏ mj 
+ · · · + ak  j=1  .
trong đó x, y đều không chia hết cho 28.
13

Lờigiải. Tacó28=4·7vàgcd(4,7)=1.Ápdụnghệquả2.1.8choa=4, b = 7 (φ(4) = 2, φ(7) = 6), ta được:
• Chọnm=1,n=5thì
710 +46 ≡ 1 (mod 28).
Do đó, x = 72,y = 4 là một nghiệm của phương trình ban đầu.
• Chọnm=5,n=6thì
430 + 712 ≡ 1 (mod 28).
Do đó, x = 46, y = 72 là một nghiệm của phương trình ban đầu.
Vậy, phương trình đồng dư trên có ít nhất 2 nghiệm (x, y) = (72, 4); (46, 72). Bài toán 2. Chứng minh rằng tồn tại các số nguyên dương x, y, z không chia
hết cho 60, thỏa mãn:
x16 +y16 +z16 ≡ 1 (mod 60).
Lờigiải. Do60=3·4·5,nêntachọn
q1 =3·4=12,q2 =3·5=15,q3 =4·5=20.
Áp dụng hệ quả 2.1.10 cho n = 16, ta có
1216 +1516 +2016 ≡ (12+15+20)16 ≡ 4716 (mod 60).
Lại vì φ(60) = φ(3) · φ(4) · φ(5) = 16 và gcd(47, 60) = 1 nên 4716 ≡ 1 (mod 60).
Từ đó chọn x = 12, y = 15, z = 20 ta có điều cần chứng minh.
Nhận xét. Bài toán vẫn đúng nếu ta thay số mũ 16 thành 4, vì ta dễ kiểm tra
theo đồng dư thì 474 ≡ 1 (mod 60).
Bài toán 3. Chứng minh rằng hệ phương trình đồng dư sau có nghiệm
(x, y, z, t) nguyên dương:
xt +yt +zt ≡ 1 (mod 1155)
.
x, y, z ̸≡ 0 (mod 1155)
14

Chứngminh. Tươngtựbài2,vì1155=7·11·15nêntacó 77t + 105t + 165t ≡ 347t (mod 1155).
Vì gcd(347, 1155) = 1 nên chọn
t = φ(1155) = φ(3) · φ(5) · φ(7) · φ(11) = 480,
ta có
Chọn (x, y, z, t) = (77, 105, 165, 480) ta có điều cần chứng minh.
2.2.2. Các bài toán về chứng minh sự tồn tại, không tồn tại
Bài toán 4. Cho k ∈ Z+ thỏa mãn gcd(k, 10) = 1. Chứng minh rằng tồn tại
vô hạn số hạng của dãy chia hết cho k.
1,11,111,1111,··· ,
77480 + 105480 + 165480 ≡ 347480 ≡ 1 (mod 1155).
Chứng minh. Các số hạng của dãy trên đều có dạng 10n − 1. Ta sẽ chứng n9
minhtồntạivôhạnnđể10 −1chiahếtcho9k.Rõràngvìgcd(10,k)=1 nêngcd(10,9k)=1.Thếthìvớimọin=aφ(9k)vớia∈Z+ bấtkì,tacó
10aφ(9k) ≡ 1 (mod 9k), dẫn đến điều cần chứng minh.
Bài toán 5. Chứng minh rằng với mọi số nguyên dương m, tồn tại số nguyên dương n có tổng các chữ số bằng m và chia hết cho m.
Phân tích. Thông thường với bài toán như thế này, ta sẽ tìm số n chỉ gồm m chữ số 1 và một số hữu hạn chữ số 0, do đó n sẽ có dạng
n = 10a1 +10a2 +···+10am,
vớia1 < a2 < ··· < am.Đếnđây,nếumỗi10ai đềuđồngdưvới1theo modulo m thì ta có điều cần chứng minh.
15

Chứng minh. Trước hết ta xét trường hợp gcd(m, 10) = 1.
Khi đó, chọn n = 10φ(m) + 102φ(m) + · · · + 10mφ(m), thì tổng các chữ số của n bằng m, và theo định lí Euler ta có
n ≡ 1+1+···+1 = m (mod m),
Nếu gcd(m, 10) > 1, đặt m = 2a · 5b · m′, với gcd(m′, 10) = 1. Khi đó, ta chọn
n = 10φ(m′) + 102φ(m′) + · · · + 10mφ(m′) · 10c, với c = max{a, b} thì n có tổng các chữ số bằng m, và
 2 a · 5 b n
n≡1+1+···+1≡m≡0 (modm′)
hay suy ra m n.
Bài toán 6. Cho n > 3 là một số nguyên dương lẻ. Chứng minh rằng tồn tại
một số nguyên tố p là ước của 2φ(n) − 1, nhưng không là ước của n.
Phân tích. Vì n lẻ nên n 2φ(n) − 1. Do đó, ta cần chứng minh tập ước nguyên
tố của 2φ(n) − 1 chứa 1 phần tử ngoài tập ước nguyên tố của n.
Chứng minh. Trước hết, ta xét n = qk, với q ∈ P. Khi đó φ(n) = qk−1(q − 1)
chẵn và φ(n) ≥ 4. Vì thế
φ(n)  φ(n)  φ(n) 
2−1=22−122+1.
Hai nhân tử bên vế phải đều lớn hơn 1 và nguyên tố cùng nhau, do đó phải
cóítnhất1nhântửcóướcnguyêntốpkhácqvàvìthếp̸ n.
Nếu n có từ 2 ước nguyên tố lẻ q1, q2 trở lên, thì 4 φ(q1)φ(q2) φ(n).
Khiđó,vớimỗiướcnguyêntốlẻqcủanthìq−1 φ(n).TheođịnhlíFermat
haym n.
,
nhỏ thì
2
2
q 2q−1−1 2φ(n)−1.