Chuyên đề bồi dưỡng học sinh giỏi Toán THPT phần Số học - Tác giả Hà Huy Khoái

Khám phá chuyên đề bồi dưỡng học sinh giỏi toán trung học phổ thông với các kiến thức và bài tập số học phong phú, giúp nâng cao kỹ năng toán học.

• Đề tài: Chuyên Đề Bồi Dưỡng Học Sinh Giỏi Toán Trung Học Phổ Thông Số Học

Mục lục chi tiết

• LỜI NÓI ĐẦU
• 1. CHƯƠNG 1: LÍ THUYẾT CHIA HẾT
• 1.1. Nguyên lí quy nạp toán học
• 1.2. Tính chia hết
• 1.3. Biểu diễn số nguyên
• 1.4. Số nguyên tố
• 1.5. Ước chung lớn nhất. Thuật toán Ơ-clít
• 1.5.1. Ước chung lớn nhất
• 1.5.2. Thuật toán Ơ-clít

Tóm tắt

I. Tổng quan chuyên đề bồi dưỡng HSG toán số học THPT

Số học là một trong những lĩnh vực toán học cổ xưa và nền tảng nhất, nhưng cũng là nơi tồn tại nhiều giả thuyết lớn chưa có lời giải đáp. Quá trình tìm kiếm lời giải cho các giả thuyết này đã thúc đẩy sự ra đời của nhiều lý thuyết toán học vĩ đại. Ngày nay, Số học không chỉ giới hạn trong toán học lý thuyết mà còn có vô số ứng dụng thực tiễn, đặc biệt trong ngành bảo mật thông tin và mật mã học. Do đó, việc trang bị kiến thức nền tảng và nâng cao về Số học cho học sinh ngay từ bậc phổ thông là cực kỳ cần thiết. Một đặc điểm thuận lợi của lĩnh vực này là nhiều thành tựu quan trọng có thể được tiếp cận chỉ với kiến thức phổ thông được nâng cao. Điều này tạo cơ hội để học sinh nhanh chóng tiếp cận với khoa học hiện đại. Chuyên đề bồi dưỡng học sinh giỏi toán số học được xây dựng nhằm hệ thống hóa kiến thức, từ những khái niệm cơ bản nhất như lý thuyết chia hết đến các công cụ mạnh mẽ như lý thuyết đồng dư. Mục tiêu của chuyên đề không chỉ là cung cấp lý thuyết mà còn rèn luyện tư duy giải quyết vấn đề, giúp học sinh tự tin chinh phục các bài toán khó trong các kỳ thi học sinh giỏi quốc gia và quốc tế. Nội dung được trình bày một cách có hệ thống, đi từ các nguyên lý cơ bản, các định lý quan trọng, đến việc áp dụng vào giải các bài tập chọn lọc. Cách tiếp cận này giúp học sinh xây dựng một nền tảng vững chắc, từ đó phát triển khả năng tự nghiên cứu và khám phá các vấn đề sâu hơn trong Số học. Chuyên đề nhấn mạnh việc hiểu sâu bản chất của vấn đề thay vì chỉ học thuộc lòng các công thức, qua đó khơi dậy niềm đam mê và khả năng sáng tạo của học sinh.

1.1. Tầm quan trọng của Số học trong toán học hiện đại

Số học, từ một ngành toán học thuần túy, đã trở thành trụ cột cho nhiều lĩnh vực công nghệ cao. Theo tác giả Hà Huy Khoái, Số học "là lĩnh vực có rất nhiều ứng dụng, đặc biệt trong lĩnh vực bảo mật thông tin". Các hệ mật mã khóa công khai, nền tảng của giao dịch điện tử an toàn, đều dựa trên các bài toán số học khó như phân tích một số nguyên lớn ra thừa số nguyên tố. Việc nghiên cứu các số nguyên tố, tính chất của chúng, và sự phân bố của chúng không chỉ là một bài toán lý thuyết mà còn mang tính thời sự. Hơn nữa, các khái niệm như đồng dư và các định lý như Định lý Phecma bé là công cụ không thể thiếu trong khoa học máy tính, lý thuyết mã hóa và thuật toán. Việc bồi dưỡng kiến thức này cho học sinh giỏi không chỉ giúp các em đạt thành tích cao mà còn chuẩn bị hành trang để tiếp cận các ngành khoa học và công nghệ tiên tiến trong tương lai.

1.2. Mục tiêu của chuyên đề bồi dưỡng cho học sinh giỏi

Chuyên đề này đặt ra ba mục tiêu chính. Thứ nhất, hệ thống hóa một cách đầy đủ và sâu sắc các kiến thức cốt lõi của Số học phổ thông, bao gồm lý thuyết chia hết, lý thuyết đồng dư, các định lý nền tảng và các hàm số học quan trọng. Thứ hai, cung cấp một nguồn bài tập chọn lọc phong phú, được phân loại từ cơ bản đến nâng cao, giúp học sinh củng cố lý thuyết và rèn luyện kỹ năng giải toán. Các bài tập này được tuyển chọn từ các kỳ thi học sinh giỏi, đảm bảo mức độ thử thách và tính thực tiễn. Thứ ba, và quan trọng nhất, chuyên đề hướng tới việc hình thành phương pháp giải toán và tư duy sáng tạo. Thay vì chỉ đưa ra lời giải, chuyên đề khuyến khích học sinh tự đặt câu hỏi "tại sao lại giải như vậy?", từ đó nắm bắt được phương pháp luận để giải quyết một lớp bài toán, chứ không chỉ một bài toán cụ thể.

II. Những thách thức khi học số học ở bậc trung học phổ thông

Mặc dù có tầm quan trọng lớn, Số học lại là một trong những mảng kiến thức gây nhiều khó khăn nhất cho học sinh THPT, kể cả học sinh chuyên toán. Một trong những thách thức lớn nhất đến từ chính chương trình giáo dục phổ thông. Tác giả Hà Huy Khoái nhận định: "trong chương trình Số học ở trường phổ thông hiện nay, môn Số học chưa được giành nhiều thời gian". Sự thiếu hụt này dẫn đến việc học sinh không được trang bị đầy đủ các công cụ lý thuyết một cách hệ thống, khiến các em cảm thấy lúng túng khi đối mặt với các bài toán số học trong các kỳ thi. Các bài toán này thường đòi hỏi sự vận dụng linh hoạt nhiều mảng kiến thức khác nhau, từ lý thuyết chia hết, số nguyên tố, đến lý thuyết đồng dư. Thách thức thứ hai nằm ở tính trừu tượng và sự đa dạng của các phương pháp giải. Không giống như các phần khác của toán học có công thức và thuật toán rõ ràng, bài toán số học thường yêu cầu những nhận xét tinh tế, những cách biến đổi khéo léo và đôi khi là những ý tưởng độc đáo. Việc thiếu một lộ trình bồi dưỡng học sinh giỏi toán số học bài bản khiến học sinh dễ bị "ngợp" trước kho tàng kiến thức và các dạng bài tập. Nhiều em chỉ học được cách giải các bài toán cụ thể mà không hiểu được phương pháp luận đằng sau, dẫn đến việc không thể giải quyết các bài toán biến thể hoặc các vấn đề mới. Do đó, một chuyên đề bồi dưỡng hiệu quả cần phải giải quyết được những thách thức này.

2.1. Hạn chế về thời lượng và chiều sâu trong chương trình

Chương trình toán học phổ thông thường chỉ giới thiệu các khái niệm cơ bản về tính chia hết và số nguyên tố ở mức độ sơ lược. Các công cụ mạnh mẽ hơn như lý thuyết đồng dư, định lý Trung Quốc về phần dư, hay định lý Phecma bé thường không được giảng dạy hoặc chỉ được đề cập qua loa. Điều này tạo ra một khoảng trống kiến thức lớn. Học sinh muốn chinh phục các kỳ thi học sinh giỏi bắt buộc phải tự tìm tòi, học hỏi từ các nguồn tài liệu tham khảo bên ngoài. Sự thiếu tính hệ thống này làm cho quá trình tự học trở nên khó khăn và thiếu định hướng, ảnh hưởng trực tiếp đến kết quả của việc bồi dưỡng học sinh giỏi toán số học.

2.2. Các dạng toán khó thường gặp trong kỳ thi học sinh giỏi

Các kỳ thi học sinh giỏi quốc gia và quốc tế thường có những bài toán số học rất khó, đòi hỏi tư duy bậc cao. Các dạng toán phổ biến bao gồm: phương trình nghiệm nguyên (phương trình Diophantine), chứng minh các tính chất chia hết phức tạp, bài toán liên quan đến số chính phương, các bài toán về hàm số học, và các bài toán tồn tại. Để giải quyết chúng, học sinh cần nắm vững không chỉ lý thuyết chia hết và số nguyên tố mà còn phải biết kết hợp chúng với các công cụ từ lý thuyết đồng dư, bất đẳng thức, hay thậm chí là tổ hợp. Sự phức tạp và tổng hợp này chính là rào cản lớn nhất đối với nhiều học sinh.

III. Nền tảng với lý thuyết chia hết và các số nguyên tố

Để chinh phục các bài toán số học, việc xây dựng một nền tảng vững chắc về lý thuyết chia hết và các tính chất của số nguyên tố là bước đi đầu tiên và quan trọng nhất. Đây là những viên gạch cơ bản tạo nên toàn bộ cấu trúc của Số học. Chuyên đề bồi dưỡng học sinh giỏi toán số học bắt đầu với việc hệ thống hóa lại các khái niệm nền tảng này một cách chặt chẽ. Từ định nghĩa về phép chia hết, các tính chất cơ bản, đến thuật toán chia (Division Algorithm), học sinh sẽ được trang bị những công cụ sơ đẳng nhưng vô cùng hiệu quả. Một trong những công cụ chứng minh hữu hiệu nhất là nguyên lý quy nạp toán học. Nguyên lý này không chỉ dùng để chứng minh các mệnh đề mà còn là cơ sở để định nghĩa các hàm đệ quy, một khái niệm quan trọng trong số học và khoa học máy tính. Tiếp theo, chuyên đề đi sâu vào khái niệm số nguyên tố – những "nguyên tử" của thế giới số nguyên. Học sinh sẽ được tìm hiểu về Định lý cơ bản của Số học, khẳng định rằng mọi số nguyên dương lớn hơn 1 đều có thể được phân tích duy nhất thành tích các thừa số nguyên tố. Định lý này là chìa khóa để giải quyết vô số bài toán liên quan đến ước số, bội số, ước chung lớn nhất (UCLN) và bội chung nhỏ nhất (BCNN). Cuối cùng, thuật toán Euclid, một thuật toán cổ xưa nhưng vẫn giữ nguyên giá trị, được giới thiệu như một phương pháp hiệu quả để tìm UCLN của hai số nguyên mà không cần phân tích chúng ra thừa số nguyên tố.

3.1. Nguyên lý quy nạp toán học và thuật toán chia

Nguyên lý quy nạp toán học là một công cụ chứng minh mạnh mẽ, dựa trên "Tính chất sắp xếp thứ tự tốt" của tập hợp số nguyên dương. Để chứng minh một mệnh đề đúng với mọi số nguyên dương, ta chỉ cần chứng minh nó đúng với trường hợp cơ sở (thường là n=1) và chứng minh rằng nếu nó đúng với n thì cũng đúng với n+1. Bên cạnh đó, thuật toán chia phát biểu rằng với hai số nguyên a và b (b>0), tồn tại duy nhất các số nguyên q (thương) và r (dư) sao cho a = bq + r, với 0 ≤ r < b. Đây là định lý nền tảng cho mọi khái niệm về chia hết và đồng dư sau này.

3.2. Định lý cơ bản của số học và ứng dụng phân tích

Định lý cơ bản của Số học là một trong những trụ cột của lý thuyết số. Nó khẳng định tính duy nhất của việc phân tích một số nguyên dương thành tích các lũy thừa của các số nguyên tố. Ví dụ, số 60 luôn được phân tích thành 2² ⋅ 3¹ ⋅ 5¹ và không có cách nào khác. Ứng dụng của định lý này rất rộng rãi, từ việc tìm UCLN và BCNN thông qua dạng phân tích tiêu chuẩn, đến việc xác định số lượng ước số của một số nguyên. Việc nắm vững định lý này giúp học sinh có cái nhìn sâu sắc về cấu trúc của các số nguyên.

3.3. Khám phá thuật toán Euclid và ước chung lớn nhất

Tìm ước chung lớn nhất (UCLN) của hai số lớn bằng cách phân tích ra thừa số nguyên tố có thể rất khó khăn. Thuật toán Euclid cung cấp một phương pháp hiệu quả hơn nhiều. Thuật toán này dựa trên nhận xét rằng (a, b) = (b, r), trong đó r là phần dư của a khi chia cho b. Bằng cách áp dụng liên tiếp thuật toán chia, ta sẽ đi đến phần dư khác không cuối cùng, đó chính là UCLN. Hơn nữa, thuật toán Euclid mở rộng còn cho phép biểu diễn UCLN dưới dạng một tổ hợp tuyến tính của a và b, tức là d = ma + nb, một kết quả có ý nghĩa quan trọng trong việc giải phương trình nghiệm nguyên.

IV. Phương pháp giải toán đỉnh cao bằng lý thuyết đồng dư

Nếu lý thuyết chia hết là nền móng, thì lý thuyết đồng dư chính là bộ công cụ cao cấp giúp giải quyết các bài toán số học phức tạp một cách thanh lịch và hiệu quả. Đây là một phần không thể thiếu trong chuyên đề bồi dưỡng học sinh giỏi toán số học THPT. Khái niệm "đồng dư mô-đun m", ký hiệu a ≡ b (mod m), thực chất là một cách phân loại các số nguyên vào các lớp khác nhau dựa trên số dư của chúng khi chia cho m. Việc làm việc với các lớp đồng dư này thay vì các số nguyên cụ thể giúp đơn giản hóa bài toán một cách đáng kể. Chuyên đề sẽ trình bày chi tiết về các tính chất của quan hệ đồng dư, cách thực hiện các phép toán cộng, trừ, nhân trên các đồng dư. Một nội dung quan trọng là giải đồng dư tuyến tính dạng ax ≡ b (mod m). Việc tìm nghiệm của đồng dư này có liên quan mật thiết đến việc tìm nghịch đảo mô-đun và giải phương trình Diophantine tuyến tính. Các định lý lớn như Định lý Trung Quốc về phần dư, Định lý Phecma bé và Định lý Wilson là những công cụ cực kỳ mạnh mẽ. Định lý Trung Quốc cho phép giải quyết một hệ các đồng dư tuyến tính với các mô-đun nguyên tố cùng nhau. Trong khi đó, Định lý Phecma bé (a^(p-1) ≡ 1 (mod p)) là chìa khóa để giải quyết các bài toán liên quan đến lũy thừa và tìm số dư, đồng thời là nền tảng cho các thuật toán kiểm tra tính nguyên tố.

4.1. Khái niệm đồng dư và hệ thặng dư đầy đủ

Hai số nguyên a và b được gọi là đồng dư với nhau mô-đun m nếu chúng có cùng số dư khi chia cho m, hay nói cách khác m | (a - b). Quan hệ đồng dư là một quan hệ tương đương, chia tập hợp các số nguyên thành m lớp, gọi là các lớp đồng dư. Một hệ thặng dư đầy đủ mô-đun m là một tập hợp gồm m số nguyên sao cho mỗi số trong tập hợp đại diện cho một lớp đồng dư duy nhất. Ví dụ, tập {0, 1, 2, ..., m-1} là hệ thặng dư không âm bé nhất. Hiểu rõ khái niệm này là bước đầu tiên để vận dụng lý thuyết đồng dư.

4.2. Giải quyết đồng dư tuyến tính và Định lý Trung Quốc

Đồng dư tuyến tính ax ≡ b (mod m) có nghiệm khi và chỉ khi UCLN(a, m) là ước của b. Nếu điều kiện này thỏa mãn, sẽ có đúng d = UCLN(a, m) nghiệm không đồng dư mô-đun m. Trong khi đó, Định lý Trung Quốc về phần dư cung cấp một phương pháp để tìm nghiệm duy nhất (mô-đun M) cho một hệ các đồng dư, ví dụ: x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂),..., với các mᵢ nguyên tố cùng nhau từng đôi. Định lý này có ứng dụng sâu rộng từ lý thuyết đến thực tiễn, như trong bài toán "Hàn Tín điểm binh".

4.3. Vận dụng Định lý Phecma bé và Định lý Wilson

Định lý Phecma bé là một trong những kết quả đẹp và hữu ích nhất của số học. Nó phát biểu rằng nếu p là một số nguyên tố và a là số nguyên không chia hết cho p, thì a^(p-1) ≡ 1 (mod p). Định lý này giúp rút gọn các lũy thừa bậc cao trong các bài toán tìm số dư. Một định lý quan trọng khác là Định lý Wilson, khẳng định rằng một số nguyên p > 1 là số nguyên tố khi và chỉ khi (p-1)! ≡ -1 (mod p). Mặc dù ít được dùng để tính toán trực tiếp, định lý này là một công cụ chứng minh lý thuyết rất mạnh mẽ.

V. Ứng dụng và các dạng bài tập số học chọn lọc nâng cao

Sau khi đã nắm vững các công cụ lý thuyết, bước tiếp theo trong quá trình bồi dưỡng học sinh giỏi toán số học là áp dụng chúng vào giải quyết các bài toán thực tế. Chuyên đề dành một phần quan trọng để giới thiệu các dạng toán nâng cao và các chủ đề đặc biệt, thường xuất hiện trong các kỳ thi cấp quốc gia và quốc tế. Các hàm số học như hàm phần nguyên, hàm số các ước d(n), hàm tổng các ước σ(n) là những đối tượng nghiên cứu thú vị. Bên cạnh đó, việc tìm hiểu về các con số đặc biệt như số hoàn hảo, số Mersenne, hay số Fermat không chỉ mở rộng kiến thức mà còn cho thấy vẻ đẹp và sự bí ẩn của số học. Chẳng hạn, giả thuyết về sự tồn tại vô hạn các số nguyên tố Mersenne vẫn là một bài toán mở. Một phần không thể thiếu của chuyên đề là tuyển tập các bài tập tổng hợp. Các bài tập này được thiết kế để học sinh phải vận dụng linh hoạt nhiều kiến thức từ lý thuyết chia hết, lý thuyết đồng dư đến các nhận xét tinh tế khác. Theo tác giả Hà Huy Khoái, đây là những bài tập "có mức độ gần như các bài tập thường được cho trong các kì thi chọn học sinh giỏi quốc gia và quốc tế". Việc luyện tập với các bài toán này giúp học sinh làm quen với áp lực và yêu cầu tư duy của các kỳ thi thật, đồng thời nâng cao khả năng phân tích và tổng hợp vấn đề. Quá trình giải bài tập nâng cao chính là cơ hội tốt nhất để học sinh biến kiến thức lý thuyết thành kỹ năng thực chiến.

5.1. Các hàm số học và những con số đặc biệt

Chuyên đề giới thiệu một số hàm số học cơ bản và các tính chất của chúng. Ngoài ra, học sinh sẽ được khám phá các loại số nổi tiếng trong lịch sử toán học. Số Fermat, có dạng Fₙ = 2^(2ⁿ) + 1, có liên quan đến bài toán dựng đa giác đều bằng thước và compa. Số Mersenne, có dạng Mₚ = 2ᵖ - 1 (với p là số nguyên tố), lại liên quan chặt chẽ đến việc tìm kiếm các số hoàn hảo chẵn (số bằng tổng các ước thực sự của nó). Những chủ đề này mang lại sự hứng thú và chiều sâu cho việc học số học.

5.2. Tuyển tập bài tập tổng hợp từ các kỳ thi

Phần này bao gồm hơn 100 bài tập nâng cao có lời giải chi tiết. Các bài toán được lựa chọn cẩn thận để bao quát các dạng thường gặp: chứng minh chia hết, phương trình nghiệm nguyên, số chính phương, bất đẳng thức số học, và các bài toán về cấu trúc số. Việc phân tích lời giải giúp học sinh học hỏi các kỹ thuật và phương pháp giải điển hình. Quan trọng hơn, như tác giả Hà Huy Khoái nhấn mạnh, học sinh nên "cố gắng tự mình trả lời câu hỏi tại sao lại phải giải như vậy", để từ đó học được một phương pháp giải, chứ không chỉ là cách giải một bài toán cụ thể.

Nội dung chính

Chuyên đề bồi dưỡng học sinh giỏi Toán THPT: Số học – GS. Hà Huy Khoái

Tổng quan về giáo trình

Tài liệu học thuật Chuyên đề bồi dưỡng học sinh giỏi Toán THPT: Số học do Giáo sư Hà Huy Khoái biên soạn, được Nhà xuất bản Giáo dục ấn hành (Mã số: 8l023N4 - CNĐ GD - 04). Trong hệ thống đào tạo toán học, Số học (Lý thuyết số) giữ vị trí nền tảng, kết nối toán học cổ điển với các cấu trúc đại số trừu tượng và khoa học máy tính hiện đại. Mặc dù đóng vai trò trọng yếu trong các kỳ thi học sinh giỏi quốc gia và quốc tế, thời lượng dành cho phân môn này trong chương trình phổ thông tiêu chuẩn còn hạn chế. Giáo trình này được xây dựng nhằm giải quyết khoảng trống đó, phục vụ công tác giảng dạy của giáo viên chuyên Toán và đào tạo học sinh chuyên, sinh viên đại học khối ngành Toán – Tin.

Mục tiêu học tập của giáo trình bao gồm:

• Trang bị hệ thống lý thuyết số từ sơ cấp đến nâng cao một cách chặt chẽ và chuẩn xác.
• Phát triển tư duy thuật toán và kỹ năng chứng minh toán học thông qua các phương pháp quy nạp, phản chứng và cấu trúc đại số.
• Xây dựng cầu nối kiến thức giữa toán học thuần túy với các lĩnh vực ứng dụng hiện đại, đặc biệt là mật mã học và khoa học máy tính.

Cấu trúc giáo trình được tổ chức thành hai phần chính:

1. Phần I: Những kiến thức cơ bản: Trình bày hệ thống lý thuyết theo từng chương, đi kèm hơn 200 bài tập cuối chương không có lời giải nhằm rèn luyện tính độc lập trong tư duy.
2. Phần II: Bài tập tổng hợp: Tuyển chọn hơn 100 bài toán có mức độ tương đương các kỳ thi học sinh giỏi quốc gia (VMO) và quốc tế (IMO), đi kèm lời giải chi tiết mang tính định hướng phương pháp.

Cách tiếp cận của tác giả mang tính sư phạm chặt chẽ, khởi đầu từ các tiên đề cơ bản nhất của tập hợp số tự nhiên và phát triển tuần tự lên các cấu trúc phức tạp như phân số liên tục, phương trình nghiệm nguyên và dãy số Fibonacci.

---

Nội dung kiến thức cốt lõi

[Tiên đề & Chia hết] ──> [Lý thuyết Đồng dư] ──> [Hàm số học & Số nguyên tố] ──> [Phân số liên tục & Phương trình Điôphăng]
         │                          │                                │                                │
  - Quy nạp toán học         - Đồng dư tuyến tính             - Số Phecma, Mersenne            - Dãy số Fibonacci
  - Thuật toán Euclid        - Định lý Thặng dư TH            - Số giả nguyên tố               - Nghiệm nguyên bậc 2
  - Định lý cơ bản           - Fermat bé & Wilson             - Số Carmichael                  - Mật mã học & Thuật toán

Các chương và chủ đề chính

• Chương 1: Lí thuyết chia hết
  Khảo sát các nguyên lý nền tảng của số học:

  • Nguyên lí quy nạp toán học: Xây dựng từ tính chất sắp xếp thứ tự tốt (Well-ordering principle); thiết lập nguyên lý quy nạp dạng 1, dạng 2; định nghĩa các hàm đệ quy (hàm giai thừa $n!$); chứng minh công thức hệ số nhị thức $C_n^k$, đẳng thức tam giác Pascal ($C_n^k + C_{n-1}^k = C_{n+1}^k$) và định lý nhị thức Newton.
  • Tính chia hết và thuật toán chia: Chứng minh sự tồn tại và duy nhất của thương $q$ và số dư $r$ ($0 \le r < b$) trong phép chia số nguyên thông qua khái niệm phần nguyên $[x]$; mở rộng quan hệ chia hết trên tổ hợp tuyến tính $c \mid (ma + nb)$.
  • Biểu diễn số nguyên: Định lý biểu diễn số nguyên duy nhất trong cơ số $b > 1$ tổng quát ($n = \sum_{j=0}^k a_j b^j$), khảo sát hệ thập phân, hệ nhị phân ($b=2$), hệ cơ số 60 (Babilon) và cơ số 12 (Maia).
  • Số nguyên tố: Chứng minh tính vô hạn của tập hợp số nguyên tố; định lý ước nguyên tố không vượt quá $\sqrt{n}$; kỹ thuật sàng Eratosthenes; tổng quan phân bố số nguyên tố qua Định lý số nguyên tố $\pi(x) \sim x / \ln x$ (Gauss, de la Vallée-Poussin); khảo sát dãy $n$ hợp số liên tiếp $(n+1)!+2, \dots, (n+1)!+n+1$ và Giả thuyết Goldbach (1742).
  • Ước chung lớn nhất và Thuật toán Ơ-clít: Định nghĩa $(a, b)$, khái niệm nguyên tố cùng nhau; chứng minh ước chung lớn nhất là tổ hợp tuyến tính dương nhỏ nhất $d = ma + nb$ (Định lý Bézout); thuật toán chia Euclid liên tiếp để tìm ƯCLN.
  • Định lí cơ bản của số học: Chứng minh phân tích thừa số nguyên tố duy nhất; bổ đề Euclid ($p \mid ab \Rightarrow p \mid a$ hoặc $p \mid b$); công thức biểu diễn ƯCLN $(a, b) = \prod p_i^{\min(a_i, b_i)}$ và BCNN $[a, b] = \prod p_i^{\max(a_i, b_i)}$; hệ thức $[a, b](a, b) = ab$.
  • Các số Phecma: Phương pháp phân tích Fermat dựa trên hiệu hai số chính phương $n = s^2 - t^2$; khảo sát số Fermat $F_n = 2^{2^n} + 1$; chứng minh tính chất $\prod_{k=0}^{n-1} F_k = F_n - 2$ và $(F_m, F_n) = 1$; ứng dụng chứng minh tính vô hạn của số nguyên tố; Định lý Gauss về điều kiện dựng đa giác đều $n$ cạnh bằng thước kẻ và compa ($n = 2^k p_1 \dots p_s$ với $p_i$ là các số nguyên tố Fermat).

• Chương 2: Lí thuyết đồng dư
  Phát triển công cụ đại số trên vành số nguyên:

  • Khái niệm cơ bản: Định nghĩa quan hệ tương đương $a \equiv b \pmod m$; phân hoạch tập số nguyên thành các lớp đồng dư; hệ thặng dư đầy đủ (hệ không âm bé nhất, hệ tuyệt đối bé nhất); các quy tắc số học trên đồng dư và điều kiện giản ước $ac \equiv bc \pmod m \Rightarrow a \equiv b \pmod{m/(c,m)}$.
  • Đồng dư tuyến tính: Điều kiện có nghiệm của phương trình $ax \equiv b \pmod m$ dựa trên $d = (a, m) \mid b$; cấu trúc nghiệm $x \equiv x_0 + (m/d)t$; khái niệm phần tử nghịch đảo modulo ($a^{-1} \pmod m$); khảo sát phần tử tự nghịch đảo modulo số nguyên tố $p$ ($a \equiv \pm 1 \pmod p$).
  • Định lí Trung Quốc về phần dư (CRT): Giải bài toán "Hàn Tín điểm binh"; chứng minh nghiệm duy nhất modulo $M = m_1 m_2 \dots m_k$; công thức tường minh $x = \sum a_i M_i y_i$; khảo sát tính chất ước chung $(2^a - 1, 2^b - 1) = 2^{(a, b)} - 1$.
  • Định lí Phecma bé và Định lí Wilson: Chứng minh định lý Wilson $(p-1)! \equiv -1 \pmod p$ cùng mệnh đề đảo; định lý Fermat bé $a^{p-1} \equiv 1 \pmod p$ ($p \nmid a$); ứng dụng tính toán nghịch đảo $a^{-1} \equiv a^{p-2} \pmod p$.
  • Số giả nguyên tố: Định nghĩa hợp số thỏa mãn $b^n \equiv b \pmod n$ (ví dụ: $341 = 11 \times 31$ với cơ sở 2); chứng minh sự tồn tại vô hạn của số giả nguyên tố cơ sở 2; khảo sát số Carmichael (hợp số giả nguyên tố với mọi cơ sở nguyên tố cùng nhau, ví dụ $561 = 3 \times 11 \times 17$) và tiêu chuẩn Korselt.
  • Ứng dụng tìm dấu hiệu chia hết: Xây dựng quy tắc chia hết trong cơ số 10 cho $2^k, 5^k, 3, 9, 11$; dấu hiệu chia hết cho 7, 11, 13 dựa trên tổng đan dấu các khối 3 chữ số; quy tắc tổng quát trong hệ cơ số $b$ bất kỳ dựa trên các ước của $b$, $b-1$ và $b+1$.

• Các chương kế tiếp (Chương 3 đến Chương 6):

  • Khảo sát các hàm số học, số hoàn hảo và số Mersenne.
  • Chương 4 (Phân số liên tục): Lý thuyết biểu diễn số thực và xấp xỉ Diophantine.
  • Chương 5 (Phương trình Điôphăng bậc 2): Ứng dụng phân số liên tục để giải các phương trình nghiệm nguyên bậc hai, phương trình dạng Pell.
  • Chương 6 (Dãy số Fibonacci): Phân tích sâu các tính chất số học, công thức truy hồi và các đồng nhất thức liên quan đến dãy số Fibonacci.

Kiến thức nền tảng được xây dựng

Lĩnh vực	Nội dung lý thuyết cốt lõi	Khung khái niệm & Định lý then chốt
Cơ sở số học	Tiên đề sắp thứ tự tốt, Quy nạp toán học	$S \subset \mathbb{N}^* \Rightarrow \exists \min S$; Quy nạp toán học dạng 1 & dạng 2; Hệ số nhị thức $C_n^k$.
Lý thuyết chia hết	Thuật toán chia, Phân tích số nguyên tố	$a = bq + r$; Bổ đề Euclid; Định lý cơ bản của số học; Sàng Eratosthenes.
Cấu trúc đồng dư	Lớp thặng dư, Đồng dư tuyến tính	$a \equiv b \pmod m$; $ax \equiv b \pmod m$; Định lý Trung Quốc về phần dư ($M = \prod m_i$).
Định lý cổ điển	Tính chất số nguyên tố & Thặng dư	Định lý Fermat bé ($a^p \equiv a$); Định lý Wilson ($(p-1)! \equiv -1$); Tiêu chuẩn Korselt cho số Carmichael.
Số học nâng cao	Xấp xỉ số thực, Dãy số & Phương trình	Phân số liên tục; Phương trình Pell / Điôphăng bậc 2; Dãy số Fibonacci; Số Fermat ($F_n$).

Kỹ năng phát triển

• Kỹ năng kỹ thuật (Technical skills): Thực hiện thành thạo thuật toán chia Euclid, thuật toán Euclid mở rộng tìm hệ số Bézout, giải hệ phương trình đồng dư tuyến tính bằng định lý số dư Trung Quốc, áp dụng phương pháp phân tích Fermat $s^2 - t^2$ cho các số nguyên lẻ.
• Kỹ năng phân tích (Analytical skills): Khả năng cấu trúc hóa bài toán số học phức tạp thành các bài toán trên hệ thặng dư modulo; vận dụng kỹ thuật quy nạp và nguyên lý thứ tự tốt để thiết lập các bất đẳng thức số học và tính chất chia hết.
• Kỹ năng ứng dụng (Practical competencies): Hiểu và triển khai các thuật toán nền tảng cho khoa học tính toán: biểu diễn số lớn, kiểm tra số nguyên tố (Primality test), số giả nguyên tố phục vụ an toàn thông tin và thuật toán mật mã hóa khóa công khai.

---

Phương pháp giảng dạy và học tập

  [Lý thuyết nền tảng]
          │
          ▼
 [Ví dụ minh họa & Chứng minh]
          │
          ▼
 [Bài tập cuối chương (200+ bài)] ──> Tự rèn luyện, không có đáp án sẵn
          │
          ▼
 [Bài tập tổng hợp (100+ bài)]   ──> Đối chiếu lời giải, phân tích phương pháp luận

Phương pháp sư phạm

Giáo trình triển khai phương pháp diễn dịch toán học chuẩn mực:

1. Thiết lập tiên đề và định nghĩa: Đảm bảo tính chính xác tuyệt đối về mặt toán học.
2. Chứng minh định lý: Mọi định lý đều đi kèm chứng minh hoàn chỉnh (ngoại trừ một số định lý vượt quá khuôn khổ sơ cấp như Định lý số nguyên tố hay định lý đảo của số Carmichael được nêu rõ ngữ cảnh lịch sử).
3. Mô hình hóa thuật toán: Chuyển hóa các chứng minh định lý thành thuật toán thực thi (như thuật toán chia, thuật toán Euclid, phương pháp Fermat, sàng Eratosthenes).

Hệ thống bài tập và thực hành

Hệ thống bài tập trong sách được phân tầng rõ rệt:

• Hơn 200 bài tập cuối các chương: Đóng vai trò củng cố lý thuyết trực tiếp của từng chương. Tác giả chủ ý không cung cấp lời giải hay chỉ dẫn cho nhóm bài tập này nhằm buộc người học phải tự liên hệ với phần lý thuyết đã học.
• Hơn 100 bài tập tổng hợp ở Phần II: Tập hợp các bài toán số học phức tạp, đòi hỏi khả năng kết hợp đa dạng các phân nhánh lý thuyết. Mỗi bài toán đều có lời giải mẫu chi tiết.

Hướng dẫn tự học và đánh giá

Đối với phần bài tập có lời giải, tác giả đưa ra chỉ dẫn phương pháp học tập quan trọng: người học không chỉ dừng lại ở việc đọc hiểu cách giải một bài toán cụ thể, mà phải tự trả lời câu hỏi "Tại sao lại phải giải như vậy?". Việc tìm kiếm nguyên nhân đằng sau hướng giải giúp người học tiếp thu được phương pháp luận toán học, đồng thời khuyến khích người học tự cải tiến, tìm kiếm các lời giải ngắn gọn và sáng sủa hơn lời giải trong sách.

---

Điểm nổi bật và cập nhật

• Bổ sung các chủ đề chuyên sâu ít xuất hiện trong sách giáo khoa chuẩn: Giáo trình cung cấp kiến thức toàn diện về các mảng khó như phân số liên tục (Chương 4), phương trình Điôphăng bậc 2 (Chương 5), dãy Fibonacci (Chương 6), số hoàn hảo và số Mersenne.
• Tích hợp bối cảnh ứng dụng hiện đại:
  • Trình bày cơ sở toán học của các hệ thống mật mã khóa công khai hiện đại dựa trên lý thuyết số nguyên tố lớn, lũy thừa đồng dư và định lý Fermat bé.
  • Minh họa cách máy tính điện tử xử lý các phép toán số học trên số nguyên cực lớn thông qua biểu diễn modulo theo Định lý Trung Quốc về phần dư (CRT).
  • Khảo sát các số giả nguyên tố và số Carmichael – những khái niệm cốt lõi trong các thuật toán kiểm tra tính nguyên tố ứng dụng trong khoa học máy tính (như thuật toán Fermat, Miller-Rabin).
• Cập nhật dữ kiện lịch sử và toán học thời sự:
  • Giới thiệu lịch sử Định lý số nguyên tố từ dự đoán của K. Gauss (1793) đến chứng minh của J. de la Vallée-Poussin (1896).
  • Nêu giả thuyết Goldbach (1742), bài toán Tháp Hà Nội của É. Lucas (1896), giả thuyết Collatz.
  • Cập nhật sự kiện chứng minh sự tồn tại vô hạn của số Carmichael vào năm 1993.

---

Đối tượng sử dụng giáo trình

• Học sinh THPT chuyên Toán và đội tuyển Học sinh giỏi: Đối tượng trực tiếp sử dụng giáo trình để bồi dưỡng kiến thức tham gia các kỳ thi chọn học sinh giỏi cấp Tỉnh/Thành phố, Quốc gia (VMO) và Quốc tế (IMO).
• Sinh viên Đại học và Học viên Cao học: Sinh viên các ngành Toán học, Sư phạm Toán học, Khoa học Máy tính, Công nghệ Thông tin, An toàn Thông tin cần tài liệu tham khảo chuẩn mực về Lý thuyết số sơ cấp và ứng dụng mật mã.
• Giáo viên và Giảng viên: Giáo viên các trường THPT chuyên sử dụng làm tài liệu biên soạn bài giảng chuyên đề, xây dựng ngân hàng đề thi học sinh giỏi; giảng viên đại học dùng làm tài liệu tham khảo cho học phần Số học và Đại số đại cương.
• Điều kiện tiên quyết: Người học chỉ cần nắm vững kiến thức toán học phổ thông nền tảng, tư duy logic cơ bản về tập hợp và phép biến đổi đại số.

---

Câu hỏi thường gặp

                        CÁC CÂU HỎI THƯỜNG GẶP (FAQ)
 ┌──────────────────────────────────────────────────────────────────────────┐
 │ 1. Giáo trình phù hợp với trình độ nào?                                  │
 │    ──> Học sinh THPT chuyên Toán, đội tuyển HSG, sinh viên Toán - Tin.   │
 ├──────────────────────────────────────────────────────────────────────────┤
 │ 2. Cần chuẩn bị kiến thức nền tảng gì trước khi đọc?                     │
 │    ──> Toán THPT cơ bản, đại số biến đổi và tư duy logic tập hợp.        │
 ├──────────────────────────────────────────────────────────────────────────┤
 │ 3. Điểm khác biệt so với các tài liệu số học phổ thông thông thường?      │
 │    ──> Phân tích sâu phân số liên tục, số giả nguyên tố, Diophantine 2.  │
 ├──────────────────────────────────────────────────────────────────────────┤
 │ 4. Làm thế nào để tự học giáo trình này hiệu quả nhất?                   │
 │    ──> Tự giải 200+ bài tập cuối chương; phân tích bản chất ở Phần II.   │
 ├──────────────────────────────────────────────────────────────────────────┤
 │ 5. Giáo trình có kèm theo lời giải toàn bộ bài tập không?                │
 │    ──> Không; 200+ bài cuối chương không giải; 100+ bài Phần II có giải. │
 └──────────────────────────────────────────────────────────────────────────┘

1. Giáo trình này phù hợp với ai?

Giáo trình được thiết kế chuyên biệt cho học sinh các lớp chuyên Toán THPT, học sinh tham gia đội tuyển thi học sinh giỏi Toán các cấp, sinh viên đại học chuyên ngành Toán – Tin, Sư phạm Toán, An toàn Thông tin và giáo viên giảng dạy chuyên đề Số học.

2. Cần kiến thức nền nào để học?

Người học chỉ cần nắm vững kiến thức đại số trong chương trình THPT tiêu chuẩn. Giáo trình xây dựng mọi lý thuyết từ các tiên đề cơ bản nhất (như tính chất sắp thứ tự tốt và nguyên lý quy nạp), không đòi hỏi kiến thức toán cao cấp phức tạp trước đó.

3. Điểm khác biệt với giáo trình khác?

Khác với các sách giáo khoa thông thường chỉ dừng ở phép chia hết và đồng dư cơ bản, giáo trình này mở rộng sâu sang các mảng chuyên đề nâng cao: phân số liên tục, phương trình Điôphăng bậc hai, dãy Fibonacci, số giả nguyên tố, số Carmichael và mối liên hệ trực tiếp với thuật toán máy tính và mật mã học.

4. Làm sao để tự học hiệu quả?

Người học nên học tuần tự lý thuyết từng chương, tự lực giải quyết hơn 200 bài tập cuối chương mà không tìm kiếm đáp án có sẵn. Khi chuyển sang hơn 100 bài tập tổng hợp ở Phần II, cần phân tích bản chất phương pháp luận đằng sau mỗi lời giải thay vì chỉ ghi nhớ các bước biến đổi cụ thể.

5. Giáo trình có cung cấp lời giải cho toàn bộ bài tập không?

Không. Giáo trình phân tách rõ ràng: hơn 200 bài tập cuối chương không có đáp án hay chỉ dẫn nhằm rèn luyện tư duy độc lập; hơn 100 bài tập tổng hợp ở Phần II được cung cấp lời giải chi tiết để hướng dẫn phương pháp giải toán nâng cao.

---

Kết luận

Chuyên đề bồi dưỡng học sinh giỏi Toán THPT: Số học của GS. Hà Huy Khoái là tài liệu học thuật có cấu trúc sư phạm chặt chẽ, kết hợp hài hòa giữa nền tảng lý thuyết số học cổ điển và định hướng ứng dụng hiện đại.

Lộ trình học tập đề xuất:

1. Nghiên cứu toàn diện các chương lý thuyết nền tảng (Chia hết, Đồng dư, Hàm số học).
2. Tự giải quyết hệ thống hơn 200 bài tập cuối chương để củng cố kỹ năng kỹ thuật.
3. Nghiên cứu sâu các chuyên đề nâng cao (Phân số liên tục, Phương trình Điôphăng bậc 2, Dãy Fibonacci).
4. Phân tích và giải quyết hơn 100 bài toán tổng hợp ở Phần II, hướng tới việc tối ưu hóa và phát triển các phương pháp giải mới.

Trích đoạn nội dung tài liệu

Chương 1. LÍ THUYẾT CHIA HẾT § 1. NGUYÊN LÍ QUY NẠP TOÁN HỌC Trước hết, ta nhắc lại tiên đề quan trọng sau đây: Tính chất sắp xếp thứ tự tốt. Môi tập không rồng các số nguyên dương đều có phản tử bé nhất.

Dựa vào tiên để nêu trên, chúng ta chứng minh được nguyên lí quy nạp toán học, là một trong những công cụ hữu hiệu nhất thường dùng khi chứng minh các mệnh đề toán học. Nguyên lí quy nạp toán học. Gia sit S la tap hợp nào đó các số nguyên dương, chứa số 1. Khi đó, nếu với mọi n € S, S đều chứa số n + 1, thì 5 là tập hợp tất cả các số nguyên dương.

Giả sử ngược lại, S không phải là tập hợp tất cả các số nguyên dương. Khi đó, tồn tại những số nguyên dương nào đó không thuộc $. Theo nguyên lí sắp thứ tự tốt, vì tập hợp các số nguyên dương không thuộc Ø là khác rồng, tồn tại số nguyên dương øœ nhỏ nhất không thuộc 6. Theo giả thiét, 1 = 1.Do n> 1 nén n —1 1486 nguyén dương nhỏ hơn 0, nén 7 —1€ §.

Nhung khi dé, (n —1)+1 =n € S, mau thudn. C] Như vậy, để chứng minh một mệnh đề nào đó đúng với tập hợp số nguyên dương, ta chỉ ra hai điều kiện. Thứ nhất, mệnh dé đúng với ø = 1. Thứ hai, nếu mệnh đề đúng với số nguyên dương ø thì cũng đúng với số nguyên dương ñ + l1.

Nguyên lí quy nạp toán học còn có dạng phát biểu thay đổi chút ít như sau. Nguyên lí quy nạp toán học thứ hai. Giả sử T là tập hợp nào đó các số nguyên dương, chứa 1. Hơn nữa, T có tính chất : nếu 1,2,.,k thuộc T thì k +1 thuộc T.

Khi đó T' là tập hợp tất cả các số nguyên đương. Gia sử 7' là tập hợp nào đó các số nguyên dương chứa 1, và nếu 1,2,., # thuộc 7' thì & -+-1 cũng thuộc 7'. Giả sử Š là tập hợp các số nguyên dương 0 sao cho mọi số nguyên dương nhỏ hơn hoặc bằng ø¡ đều thuộc 7`. Khi đó, 1€ 5, và theo giả thiết, nếu ÿ€ Š thì k+1€ 6.

Theo nguyên lí quy nạp, S là tập hợp tất cả các số nguyên dương, và do đó, 7 cũng là tập hợp tất cả các số nguyên dương. Nguyên lí quy nạp toán học cho ta một phương pháp để tìm giá trị của các hàm xác định trên tập hợp các số nguyên đương. Ta nói rằng hàm ƒ được xác định một cách đệ quy nếu giá trị của / tại | đã được cho trước, đồng thời có một quy tắc xác định ƒ(n +1) khi biết ƒ(n). Các hàm đệ quy có vai trò hết sức quan trọng trong số học, lôgich va khoa học máy tính.

Từ nguyên lí quy nạp toán học suy ra rằng, giá trị của hàm đệ quy tại mỗi số nguyên dương được xác định một cách duy nhất. Ví dụ đơn giản nhất của hàm đệ quy là hàm giải thừa (n) = nÌ được định nghĩa như sau : f0) =1; ƒ0+1)= 0 + 1)/0n). Ta quy ước 0Ì = |. Hàm giai thừa được dùng để định nghĩa các hệ số nhị thức như sau.

Giá sử m, k là các số nguyên không âm. Hệ số nhị thức +n Œ?,“im 3 cũng thường dùng kí hiệu | ; |› được định nghĩa bởi hệ thức Ch = m! m km — ky Mệnh dé 1. Gid sun va kh la cdc xố nguyên không âm, hk <n. Khi dé ) C) =ŒT =1, ti) C? =C?Tt, Chimg minh.

Ta có 1 —nÌ 3 "gu! ni! n nl n! 2 " niot ni Để thử lại H1) ta có : oe! Sox 69 nỲ nÌ nek q Œ “TM 0 BlÍn-@ứM " Một tính chất quan trọng của các hệ số nhị thức là đồng nhất thức sau : Định lí 1. Giả sử n và k là các số nguyên dương với n > k. Khi đó k k—I k C; + Cy, = Cha. Ta có on ct +c = ns + onl : so" ki(n—k)! (k—1)lín—k+1)I — mín—k+1) nk — kø=—k+l)L kÍs—k+DI — nllnu—k +1) + kị —— klm=k+D _—_ nI(n +1) _ kl(n=k+1)t — (n+1)l _ kl(n—k+1)! = Cài P Định lí 1.4 cho ta một cách xây dựng dễ dàng các số nhị thức bang tam giác Pascal.

Trong tam giác này, hệ số nhị thức Œ} là số thứ (& + 1) trong dòng (mn + 1). Sau đây là chín dòng đầu tiên của tam giác Pascal. Tam giác Pascal. ot: 86 phen “ở, v, Các số ngoài cùng của tam giác là 1.

Để có một số bên trong, ta chỉ cần lấy tổng hai số ở hàng trên ở về hai phía của vị trí đang xét. Các số nhị thức xuất hiện trong định lí nhị thức sau đây. Định lí nhị thức. Giả sir x, y ld các biến và n là số nguyên dương.

Khi đó : (c+y)" = C's" + Chr xỉ. OM ye pp $OM ey" + Otay") + Oty", tức là (c+y)" = Say), J=0 Chứng mình. Ta sử dụng nguyên lí quy nạp toán học. Do ŒÌ=Œj =1 nên trường hợp n = 1 là rõ ràng.

Giả sử định lí đúng với 0, tức là (z+}” =Y"đj. j=l Ta thử lại công thức cho trường hop n + 1. Ta co SƠ Jay) (c+ y) n+l (ety) =(e+y) (x+y)= =0 Th 11 J JapltJ_,)d+h — = › ClrJap +Š Cig yl. J=0 y= Mặt khác, , n ` Clr i) +1 yi = 2" n+l + » Cir" ¬".

3 U”, J=U J=l ?+—] n no hy gel So Cla ty + TING — 3. 4 "11, Leis Từ đó ta có : (z + gì — "1 + »e +4 Clary! + yn j=l Áp dụng định lí 1.4 ta nhận được : $y" =3 00a 7 MP n+l (z+)"”= +1 4 Chat iy! 1 1 1- ⁄ at 2 , § 2. TÍNH CHIA HẾT Dinh nghia 1. Gia st’ a, b là các số nguyên.

Ta nói ø cha hết b (hay b chia hét cho a ) nếu tồn tại số nguyên c sao cho Ö — ức. Nếu ø chia hết b, ta thường dùng kí hiệu ø|b hoặc b:ø, nếu a không chia hết b, ta viết ¿ J b hoặc b / ø. Khi ø|b, ta nói ø là ước của b. Gid sw a, b, c là các số nguyên.

Nếu a|b, b|c thì a lc. Giá sử œ, b, c, m và n là các số nguyên. Nếu c|a và c |b thì © | (ma + nh). Chứng minh các Mệnh đề 1.7 được dành cho độc giả.

Thuật toán chỉa. Giả sử a, b là các số nguyên và b > 0. Khi đó tồn tại duy nhất các số nguyên qg và r sao cho a=bq+r, D<r<b. Ta gọi ¿ là đương và r 1a phan die.

Nhu vay, a chia hét cho 6 néu va chi nếu phần dư trong phép chia bằng 0. Để chứng minh thuật toán chia, ta cần đến định nghĩa sau. Giả sử + là một số thực. Phần nguyên của z, kí hiệu qua [x], là số nguyên lớn nhất không vượt quá z.

Với mọi số thực +, œ®—1<|z]< z# Mệnh đề I.9 suy ra ngay từ định nghĩa. Chứng mình thuật toán chia. Chú ý rằng, trong chứng minh, ta sẽ cho công thức tính thương và phan du. RO rang a = bg +r.

Theo Ménh dé 1.9 ta có „1 <Ía/b]< „ Từ đó, a—b<ala/b]<a 10 suy ra Ú<r=a—Ủla/b] < È. Như vậy, z thỏa mãn tính chất đòi hỏi trong thuật toán chia. Còn phải chứng minh ¿ và r được xác định một cách duy nhất. Giả sử tacé a= bq, +7.

va @ = bq +7, trong d6 OS <b OSH < b. Trừ từng vế ta nhận được 0 =b(@ —9)+(" — T3) Suy ra y —; = b(Œ — 8).Do đó b | (7y — ?¡) nếu và chỉ nếu 1, — 7, = 0, tức là ?¡ = 7„. Suy ra q = CO § 3. BIEU DIEN SO NGUYEN Ta thường quen biểu diễn một số nguyên qua tổng các lũy thừa của 10.

Thật ra không có lí do đặc biệt nào quyết định việc đó (ngoài việc ta có 10 ngón tay Ì) Cũng có nhiều dân tộc dùng những hệ đếm khác : người Babilon dùng cơ số 60, người Maia dùng cơ số 12,. Máy tính điện tử thường dùng cơ số 2, 8 hoặc 16. Trong tiết này ta sẽ chứng tỏ rằng mọi số nguyên dương lớn hơn Ì đều có thể dùng làm cơ số. Giở sứ b là số nguyên và b > 1.

Khi đó mọi SỐ nguyên dương ¡đều có thể viết một cách duy nhất dưới dụng n= a,b" + a, be pe + a,b’ + ay, trong dé a, la sé nguyén, 0 Sa, S b, với j= 0,. Ta áp dụng liên tiếp thuật toán chia. Trước tiên chia n cho Ù, ta được : n= bq +a, 0 Sứ, <Sb—]. Lại chia qạ cho Ù, ta có : q = bạ tứ, OSa SO-1.

Tiếp tục quá trình trên, ta nhận được : il gq, = bq, + ay, O<a,<b~—1, Gy = bq3 + as, O<a, <b-1, Io = OG FH, OSG, Sb], 1 =b. Quá trình kết thúc khi ta có thương bằng Ú. Điều đó đạt được sau hữu hạn. bước, vì ?>dq, >0 >qgạ>-:.>0, và mọi dãy giảm các số nguyên không âm nhất định dừng ở 0 sau hữu hạn bước.

Như vậy ta có : tr =— bqg + dạ = b (Đại Đán) + ay = ĐỮẠp + aịb + a, = b"qy + ayb” + ab + ay =a,b* +a, bt +--+ ab + ay, trong đó 0 < a,<b-1 với 7=U,1,. Để chứng minh biểu diễn nói trên là duy nhất, ta giả thiết rằng có hai biểu diễn của ø› : n= a,b" + a,b | ++ ab + ay = c,d" + c, be" +e +ob+ 6, trong d6 0< a, <b ; OSG <b (nếu cần, ta thêm vào phía trước một trong hai biểu diễn cdc hé 86 0 dé sé tir trong hai biéu dién nhu nhau). Nếu hai biểu điễn khác nhau thì tổn tại số 7 nguyên nhỏ nhất, 0< 7< k sao cho a, = ơ„. Khi đó b2 [(% _ Cok fee (4; — Cj )| = 0, suy ra | (@, — bP +.

12 Pe Ee ` QY Đo đó a, = b| (Cx — a, prt} +. Nhung 0 < & <b ; <Sc, <b nên —b <a, —o, <b. Do dé b | (4, —¢,) chikhi a, = c,, mau thudn véi gia thiét. O Biểu diễn số ø như trong Định lí 1.10 được gọi là biểu diễn ong cơ số b.

Khi b = 2, ta thường gọi là biểu diễn nhị phân, b = 10: biểu diễn thập phán. Các hệ số a, được gọi là các chữ số của biểu diễn. Để phân biệt các biểu điển số nguyên trong các cơ số khác nhau, ta viét (a,a, ¡,., đ¡đg)y thay cho a,b° +a, jbŸ +. SO NGUYEN TO Số ] chỉ có đúng một ước dương.