Một số phương pháp giải toán số học sơ cấp

1

Một sốphương pháp giải toán sốhọc sơ cấp

Hà Duy Hưng

Tóm tắt. Lý thuyết sốcó mối liên hệgần gũi với nhiều lĩnh vực toán học khác nhau như đại số, giải tích, hình học, thậm chí cảtô pô (Ví dụmột chứng minh rất hay của Paul Erdos vềsựvô hạn của tập các sốnguyên tốdựa trên tôpô). Chính vì vậy các chứng minh sốhọc thường được dựa trên nhiều ý tưởng và nhiều phương pháp khác nhau. Bài viết này đềcập đến một sốkhái niệm cơ bản trong lý thuyết sốsơ cấp như sốmũ- một khái niệm quan trọng trong việc hình thành các số p−adic, cấp của một số- định lý Lagrange và ứng dụng trong các bài toán chia hết, hệthặng dư, nghịch đảo của một số, ... và các ứng dụng thú vịtrong giải toán sốhọc, đặc biệt trong các bài toán trong lý thuyết chia hết và đồng dư. Bài viết này dựa trên các bài giảng tôi hay sửdụng trong giảng dạy ởcác buổi chuyên đềvà tập huấn đội tuyển Olympic Toán học các cấp.

Một vài lời khuyên khi giải các bài toán SỐHỌC sơ cấp:

1. Đừng đểhình thức đánh lừa !!!

2. Ý tưởng của các chứng minh thường hay nằm ởtrong chính các chứng minh của các kết quả cơ bản.

3. Rất thường xuyên dựa vào những sựkiện đơn giản nào đấy và là phân môn có tính giải trí trí tuệcao ==> Tập trung làm hoặc biết nhiều bài toán khó, định lý mạnh không hẳn đã tốt!!!

4. Đôi khi đòi hỏi sựtưởng tượng, những tính toán bằng tay với những phép tính rất lớn!!! Ví dụ:

(a) 210 ≡107 (mod 2003) - VMO 2004,

(b) 14 ≡452 (mod 2011) - VMO 2011,

(c) (2n + 1)3 + 53 + 13 = (2n −1)3 + (n + 4)3 + (4 −n)3 - Vietnam TST 2005,

(d) 1729 = 12 + 123 = 93 + 103 - Câu chuyện giữa Hardy và Ramanujan.

Ta xét bài toán cụthểsau đây

Bài tập 0.1. (Romania TST 2011) Chứng minh rằng tồn tại vô sốsốnguyên dương n sao cho n2 + 1 có hai ước dương có hiệu đúng bằng n.

Bài toán nhìn qua có vẻkhông đơn giản, lý do biểu thức n2 + 1 có vẻkhông hềđơn giản như hình thức của nó. Ví dụbài toán xét xem liệu có vô hạn ước nguyên tốcó dạng n2 + 1 hay không đến nay vẫn là một OPEN PROBLEM!. Tuy nhiên, thực tếthì bài toán này chỉcần sửdụng hiểu biết vềmột dãy quen thuộc đó là . . .

Xem tiếp ởtrang sau . . .

www.MATHVN.com

ThuVienDeThi.com

2

dãy Fibonacci, với F0 = 0, F1 = 1, và Fn+2 = Fn+1 + Fn. Theo đẳng thức Cessani thì F 2 n+1 −Fn+2Fn = (−1)n. Do đó F 2 2k + 1 = F2k+1F2k−1. Thành thửta có thểlấy n = F2k.

Kết luận: Nên học một cách hệthống theo một giáo trình nào đó. Ví dụvềvài quyển sách sốhọc thích hợp với các học sinh và thầy cô dạy chuyên Toán:

1. Sốhọc của GS. Hà Huy Khoái.

2. Elementary Theory of Numbers of Waclaw Sierpinski

3. Number Theory of A. Baker

4. Problems in Number theory bản thảo không xuất bản của Hojoo Lee (v. 2007).

5. . . .

www.MATHVN.com

ThuVienDeThi.com

1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ 3

1 Lý thuyết chia hết và đồng dư

1.1 Tổng quan

Vấn đềlý thuyết:

1. Ước chung lớn nhất - Bội chung bé nhất. Định lý Berzout.

2. Sốnguyên tố, hợp số- Hai định lý cơ bản liên quan đến sốnguyên tố: Fermat (tổng quát: Euler) - Wilson.

3. Định lý phần (thặng) dư Trung Hoa.

Các công cụ, phương pháp giải toán trong phần này rất nhiều

1. Cấp của một sốvà ứng dụng

2. Nghịch đảo của một số

3. Hai định lý bốn sốcủa Euler.

4. Công thức Legendre - Polignac, Sốmũ.

5. Ứng dụng của các định lý cổđiển: Định lý Trung Hoa vềsựtồn tại, Định lý Fermat bé- Định lý Euler, Định lý Wilson. Bên cạnh đó một sốcác định lý cổđiễn quan trọng: như định lý Fermat vềphân loại sốnguyên tố4k ± 1.

6. Hệthặng dư đầy đủ, thu gọn.

7. Ba nguyên lý cơ bản: Nguyên lý sắp thứtựtốt, Nguyên lý Dirichlet, Nguyên lý quy nạp. Đây là ba nguyên lý thường xuyên gắn bó với lý thuyết sốvà cũng là những nguyên lý cơ bản nhất.

1.2 Cụthể

1.2.1 Ước chung lớn nhất- Định lý Berzout

Định nghĩa 1. Cho n > 1 sốnguyên không đồng thời bằng không và n sốnguyên a1, . . . , an không đồng thời bằng không. Sốnguyên d lớn nhất có tính chất d | ai với mọi i = 1, n được gọi là ước chung lớn nhất của n sốa1, . . . , an. Ta kí hiệu gcd(a1, . . . , an).

Định lý 1. (Berzout) Tồn tại các sốnguyên không x1, . . . , xn sao cho

gcd(x1, . . . …