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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:39

Thêm vào BST

Báo xấu

7
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Định lí Euler và tính dụng thực tiễn

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ương 1. ĐẶT VẤN ĐỀ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1. Lý do chọn đề tài . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2. Mục đích nghiên cứu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3. Phạm vi nghiên cứu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4. Nhiệm vụ nghiên cứu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5. Phương pháp nghiên cứu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Chương 2. NỘI DUNG NGHIÊN CỨ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. Ứng dụng vào hệ mã hóa RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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ài tập tự 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ương 3. KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.1. Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.2. Kiến nghị và đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Tài liệu tham khả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 b chia hết cho a) | A| lực lượng (số phần tử) của tập hợp A ∏ tích sigma v p ( a) số mũ đúng của a theo ước p nguyên tố a kí hiệu Legendre về thặng dư bình phương b ∑ tổng sigma A\B hiệu của tập A trừ 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
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ó 2 số nguyên dương nhỏ hơn 3 và nguyên tố cùng nhau 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ộ aa1 , aa2 , · · · , aa ϕ(n) cũng lập thành 1 HTDTG modn. Khi đó ta thu được a1 a2 · · · a ϕ(n) ≡ aa1 · aa2 · · · aa ϕ(n) = a ϕ(n) a1 a2 · · · 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ì a p −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. 2021 Ví dụ 1. Tìm số dư khi chia 2911 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ấy 112021 ≡ 3 (mod 4), nên 112021 = 4k + 3. Do đó, 2021 k 2911 = 294k+3 = 294 · 293 ≡ 293 ≡ 53 ≡ 5 (mod 12). 2021 Vậy, 2911 chia 12 được dư là 5. Chú ý. a = 4 không phải là số nguyên dương nhỏ nhất thỏa mãn 29a ≡ 1 (mod 12), vì 292 ≡ 52 ≡ 1 (mod 12). 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. ϕ pk = pk−1 ( p − 1), ∀ p ∈ P, k ∈ Z+ . (2.1) Phân tích. Để ý là gcd n, pk > 1 ⇔ gcd(n, p) > 1 ⇔ p n. Do đó, thay vì đếm số các số n nhỏ hơn pk và nguyên tố cùng nhau với pk , ta có thể đếm số các số n nhỏ hơn pk và là bội của p. 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, ϕ p k = p k − p k −1 = p k −1 ( 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 (mod m) . c ≡ b (mod n) 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ính chất 2.1.6. Nếu phân tích tiêu chuẩn của n là n = p1 1 p2 2 · · · pk k thì 1 1 1 ϕ(n) = n 1 − 1− ··· 1− , (2.2) p1 p2 pk α α α Chứng minh. Thật vậy, với n = p1 1 p2 2 · · · pnk , áp dụng 2 tính chất 2.1.4 và 2.1.5, ta có: α α α ϕ ( n ) = ϕ p1 1 ϕ p2 1 · · · ϕ p k k α −1 = p 1 1 −1 ( p 1 − 1 ) p 2 2 −1 ( p 2 − 1 ) · · · p k k α α ( p k − 1) 1 1 1 = n 1− 1− ··· 1− . p1 p2 pk 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 (mod a). Từ đó a ϕ(b) + b ϕ(a) − 1 chia hết cho cả a và b. Ta có đ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ên tố cùng nhau. Đặt M = m1 · m2 · · · mk = mi ti với i = 1, 2, 3 . . . , k, khi đó ϕ ( m1 ) ϕ ( m2 ) ϕ(mk ) t1 + t2 + . . . + tk ≡ 1 ( mod M). 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ì ϕ ( m1 ) t1 ≡1 ( modmi ) . (2.5) Mặt khác với i, j thuộc tập {1, 2, · · · , k} và i = j thì t j chia hết cho m j nên t j , mi = mi hay ϕ ( mi ) tj ≡0 ( modmi ) . (2.6) ϕ ( m1 ) ϕ ( m2 ) ϕ(mk ) Đặt S = t1 + t2 + . . . + tk . Từ (2.5) và (2.6) ta có ϕmi S ≡ ti ≡ 1 ( modmi ) . Mà m1 , m2 , · · · , mk đôi một nguyên tố cùng nhau, nên suy ra ϕ ( m1 ) ϕ ( m2 ) ϕ(mk ) t1 + t2 + . . . + tk ≡ 1 ( modm1 · m2 . . . mk ), 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ó t1 + t2 + · · · + t n ≡ ( t1 + t2 + · · · + t k ) n n n k ( mod M), 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 ≡ a1 (mod m1 )       x ≡ a (mod m )  2 2 , · · · · · · · · · · · ·       x ≡ ak (mod mk )  trong đó a1 , a2 , · · · , ak là các số nguyên bất kì, m1 , m2 , · · · , mk là các số 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ì  A ≡ 0 (mod m j ), ∀ j = i i . A ≡ a (mod mi ) i i 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   ϕ ( m1 )   ϕ ( m2 )   ϕ(mk ) k k k  ∏ mj   ∏ mj   ∏ mj   j =1   j =1   j =1  x = a1   m   + a2   m   + · · · + ak   m   .  1   2   k  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. 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ư: x 5 + y6 ≡ 1 (mod 28), trong đó x, y đều không chia hết cho 28. 13
Lời giải. Ta có 28 = 4 · 7 và gcd(4, 7) = 1. Áp dụng hệ quả 2.1.8 cho a = 4, b = 7 (ϕ(4) = 2, ϕ(7) = 6), ta được: • Chọn m = 1, n = 5 thì 710 + 46 ≡ 1 (mod 28). Do đó, x = 72 , y = 4 là một nghiệm của phương trình ban đầu. • Chọn m = 5, n = 6 thì 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ời giải. Do 60 = 3 · 4 · 5, nên ta chọ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:   x t + yt + zt ≡ 1 (mod 1155) .  x, y, z ≡ 0 (mod 1155) 14
Chứng minh. Tương tự bài 2, vì 1155 = 7 · 11 · 15 nên ta có 77t + 105t + 165t ≡ 347t (mod 1155). Vì gcd(347, 1155) = 1 nên chọn t = ϕ(1155) = ϕ(3) · ϕ(5) · ϕ(7) · ϕ(11) = 480, ta có 77480 + 105480 + 165480 ≡ 347480 ≡ 1 (mod 1155). 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 1, 11, 111, 1111, · · · , chia hết cho k. 10n − 1 Chứng minh. Các số hạng của dãy trên đều có dạng . Ta sẽ chứng 9 minh tồn tại vô hạn n để 10n − 1 chia hết cho 9k. Rõ ràng vì gcd(10, k) = 1 nên gcd(10, 9k) = 1. Thế thì với mọi n = aϕ(9k) với a ∈ Z+ bất kì, ta có 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ới a1 < a2 < · · · < am . Đến đây, nếu mỗi 10ai đều đồng dư với 1 theo 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), hay m n. 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 · 5b n , n ≡ 1 + 1 + · · · + 1 ≡ m ≡ 0 (mod m ) 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) 2 ϕ(n) − 1 = 2 2 −1 2 2 +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ó ít nhất 1 nhân tử có ước nguyên tố p khác q và 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). ϕ(n) Khi đó, với mỗi ước nguyên tố lẻ q của n thì q − 1 . Theo định lí Fermat 2 nhỏ thì ϕ(n) q 2q −1 − 1 2 2 − 1. 16
ϕ(n) Tức là mỗi ước nguyên tố của n đều là ước của 2 2 − 1, do đó không là ước ϕ(n) của 2 2 + 1. Suy ra tồn tại p nguyên tố thỏa mãn:  ϕ(n)  p 2 2 + 1 2 ϕ(n) − 1  . p  n Ta có điều cần chứng minh. Bài toán 7. (Romania TST 1997) Cho trước a > 1 là một số nguyên. Chứng minh rằng tập hợp A= a2 + a − 1, a3 + a2 − 1, · · · , ak+1 + ak − 1, · · · chứa một tập con vô hạn, sao cho các phần tử đôi một nguyên tố cùng nhau. Chứng minh. Ta sẽ chứng minh bất cứ tập con n phần tử nào của A mà có các phần tử đôi một nguyên tố cùng nhau thì có thể mở rộng thành n + 1 phần tử. Dễ thấy 2 phần tử kề nhau của A thì nguyên tố cùng nhau, nên n = 1 thỏa mãn. Với n > 1, gọi M là tích tất cả n phần tử của tập con này. Ta xét số a ϕ( M)+1 + a ϕ( M) − 1, theo định lí Euler thì a ϕ( M)+1 + a ϕ( M) − 1 ≡ a (mod M). Vì tất cả các phần tử của A đều nguyên tố cùng nhau với a nên gcd( M, a) = 1. Từ đó gcd( M, a ϕ( M)+1 + a ϕ( M) − 1) = 1, điều này dẫn đến ta có thể thêm số này vào tập con trên. Ta hoàn tất chứng minh. Bài toán 8. (China TST 2006) Chứng minh rằng với mọi m, n nguyên dương, luôn tồn tại k nguyên dương để 2k − m có ít nhất n ước nguyên tố phân biệt. Chứng minh. Đặt m = 2a m với m lẻ. Khi đó 2k − m = 2 a (2k − a − m ), nên bài toán không giảm tính tổng quát khi ta giả sử m lẻ. Đặt aa a 2k − m = p11 p22 · · · pl l 17
là phân tích tiêu chuẩn của 2k − m. Dễ thấy pi đều lẻ, do m lẻ. l Xét k1 = k + ∏ ϕ( pi i a +1 ) thì theo định lí Euler, ta có i =1 2k 1 − m ≡ 2k − m (mod piai +1 ). Tức là lúc đó v pi (2k1 − m) = v pi (2k − m) = ai , ∀i = 1, 2, · · · , l. Nhưng do k1 > k, nên rõ ràng 2k1 − m phải có ít nhất một ước nguyên tố khác p1 , p2 , · · · , pl . Rõ ràng ta có thể lặp lại thao tác này cho đến khi tìm được chỉ số j để 2k j − m có ít nhất n ước nguyên tố. Ta có điều cần chứng minh. Bài toán 9. Cho trước a1 , a2 , · · · , an là các số nguyên dương không đồng thời ∞ bằng nhau. Chứng minh rằng tập ước nguyên tố của họ a1 + a2 + . . . + ak k k n k =1 có vô hạn phần tử. Chứng minh. Ta có thể giả sử gcd ( a1 , · · · , an ) = 1. Đặt f ( k ) = a 1 + . . . + a k , k ∈ Z+ k n và giả sử phản chứng tập các ước nguyên tố của họ f (1), f (2), · · · là hữu hạn. Gọi tập đó là { p1 , . . . , pm }. Với mỗi 1 ≤ i ≤ m, đặt bi là số các số a1 , · · · , an không chia hết cho pi . Vì gcd ( a1 , · · · , an ) = 1 nên bi ≥ 1 với mọi 1 ≤ i ≤ n. Để ý rằng với m 1 + v p i ( bi ) k = 2∏ ϕ pi i =1 v p (bi )+1 ta có f (k ) ≡ bi mod pi với mọi 1 ≤ i ≤ m. Vì với mọi 1 ≤ j ≤ n thì v p (bi )+1 ak ≡ 1 mod pi j nếu a j không chia hết pi (theo định lí Euler) và v p (bi )+1 ak ≡ 0 mod pi j nếu ngược lại, do k > 1 + v p (bi ). Vì vậy v pi ( f (k )) = v pi (bi ) với mọi i và vì tất cả các ước nguyên tố của f (k) đều thuộc { p1 , p2 , · · · , p N }, ta thu được v p1 (b1 ) v p2 (b2 ) v p (b N ) f ( k ) = p1 p2 ··· pN N . 18
Từ max ( a1 , . . . , an ) ≥ 2, ta có N v p ( bi ) f ( k ) ≥ 2k > k > ∏ pi , i =1 vô lí. Dẫn đến điều cần chứng minh. 2.2.3. Các bài toán về phi hàm Euler Bài toán 10. Chứng minh rằng với mọi n ∈ Z+ thì n ϕ(2n − 1).  2d ≡ 1 (mod 2n − 1) Chứng minh. Đặt ord2n−1 (2) = d thì , suy ra 2 ϕ(2n −1) ≡ 1 (mod 2n − 1) d ϕ (2n − 1 ). Mà 2d ≡ 1 (mod 2n − 1) kéo theo 2n − 1 2d − 1. Đặt d = qn + r (q, r ∈ Nm 0 ≤ r < n) thì từ đây suy ra 2n − 1 2r − 1. Điều này chỉ xảy ra khi r = 0, tức là n|d. Do đó n ϕ(2n − 1). Bài toán 11. Cho n là số nguyên dương, n ≥ 7. Chứng minh rằng các số nguyên dương nhỏ hơn n, nguyên tố cùng nhau với n lập thành một cấp số cộng khi và chỉ khi n là số nguyên tố hoặc n = 2m (m ∈ Z+ ). Chứng minh. Gọi a1 < a2 < · · · < ak là tất cả các số nguyên tố nhỏ hơn n và nguyên tố cùng nhau với n. Chiều đảo: • Nếu n là số nguyên tố thì ( a1 , a2 , · · · , ak ) = (1, 2, · · · , n − 1), rõ ràng là một cấp số cộng. • Nếu n = 2m thì ( a1 , a2 , · · · , ak ) = (1, 3, 5, · · · , 2m − 1), cũng là cấp số cộng. 19
Chiều thuận: Rõ ràng k = ϕ(n), mà a1 = 1 nên ( a1 , a2 , · · · , ak ) = (1, 1 + t, · · · , 1 + [ ϕ(n) − 1]t) . Mặt khác, ak = n − 1, nên suy ra 1 + [ ϕ(n) − 1]t = n − 1, hay [ ϕ(n) − 1]t = n − 2. (2.7) • Nếu a2 = 2 thì t = 1, suy ra ϕ(n) = n − 1, tức là n là số nguyên tố. • Nếu a2 = 3 thì t = 2, suy ra ai = 2i − 1, ∀i = 1, 2, · · · k. Từ đó ta thấy n không có ước nguyên tố lẻ, nên n = 2k . • Nếu a2 > 3 thì 2 | n, 3 | n, nên 6 | n. Từ đó 2 | ai , 3 | ai , ∀i = 2, · · · k. Mà từ (2.7), n − 2 = ( a2 − 1)( ϕ(n) − 1), nên a2 − 1 không chia hết cho 3, do đó a2 ≡ 2 (mod 3). Từ đó a3 = 1 + 2t = 1 + 2( a2 − 1) chia hết cho 3 (vô lí). Vậy ta có điều cần chứng minh. Bài toán 12. Chứng minh rằng với mọi n là hợp số, n = 6, ta luôn có: √ √ n ≤ ϕ(n) ≤ n − n. Chứng minh. Xét phân tích tiêu chuẩn của n: aa a n = p11 p22 · · · pkk , √ với p1 < p2 < · · · < pk . Do n là hợp số nên p1 ≤ n. Khi đó, theo tính chất 2.1.6, ta có: 1 1 1 ϕ(n) = n 1 − 1− ··· 1− , p1 p2 pk suy ra 1 1 √ ϕ(n) ≤ n 1 − ≤ n 1− √ = n− n. p1 n Với chiều bất đẳng thức còn lại, ta xét các khả năng sau: 20