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 nsao 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
www.MATHVN.com
2
dãy Fibonacci, với F0= 0, F1= 1, và Fn+2 =Fn+1 +Fn. Theo đẳng thức Cessani
thì F2
n+1 −Fn+2Fn= (−1)n. Do đó F2
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
www.MATHVN.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 > 1số nguyên không đồng thời bằng không và nsố nguyên a1, . . . , ankhông
đồng thời bằng không. Số nguyên dlớn nhất có tính chất d|aivới mọi i=1, n được gọi là ước
chung lớn nhất của nsố 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, . . . , xnsao cho
gcd(x1, . . . , xn) =
n
X
i=1
xiai
Đặc biệt ta suy ra một số nguyên Nbiểu diễn được ở dạng n
P
i=1
xiaikhi và chỉ khi gcd(a1, . . . , an)|N.
Một hệ quả nữa là UCLN chia hết cho mọi ước chung.
Liên quan đến kết quả trên là bài toán đổi tiền rất nổi tiếng của Frobenius như sau: Ta có nđồng
xu với các mệnh giá a1, . . . , anlà các số nguyên dương và nguyên tố cùng nhau. Ta cần xác định số
tiền lớn nhất không thể đổi được thành các đồng xu trên. Bài toán tương đương với việc tìm số N
www.MATHVN.com
www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ 4
lớn nhất để phương trình n
P
i=1
xiai=Nvô nghiệm nguyên không âm. Việc xác định giá trị lớn nhất
đến nay vẫn là một bài toán mở. Tuy nhiên ta có một số kết quả khá đơn giản sau:
Định lý 2. 1. Trường hợp n= 2 được giải bởi Sylvester năm 1880: số Nlớn nhất là N=
a1a2−a1−a2.
2. Bài toán có nghĩa khi n > 2: chẳng hạn N≤(n−1)a1···an.
Sau đây là một số kết quả đơn giản rất đáng lưu ý.
Định lý 3. 1. Nếu (a, b) = 1 thì (am+bn, asbt) = 1 với s, t nguyên không âm, m, n nguyên dương.
2. BCNN (a, b) = ab
(a, b)
3. a≥(a, b)·(a, c)
(a, b, c).
4. gcd ap+bp
a+b, a +b=(1nếu p∤a+b
pnếu p|a+b. ở đây plà số nguyên tố lẻ, (a, b) = 1.
5. gcd an−1
a−1, a −1= gcd (n, a −1) với mọi a > 1và nnguyên dương.
6. Tính chất của dãy Mersen: gcd(am−1, an−1) = a(m,n)−1với a > 1và các số nguyên dương
m, n.
Định lý 4. (Bốn số) Nếu a, b, c, d là các số nguyên khác không thỏa mãn ab =cd. Khi đó tồn tại
x, y, z, t nguyên sao cho
a=xy
b=tz
c=xz
d=ty
(y, z) = 1.
(nếu a, b, c, d dương thì x, y, z, t cũng có thể lấy là dương)
Sau đây là một số bài toán liên quan:
Bài tập 1.1. (Germany 2008) Cho a, b, c là các số nguyên dương thỏa mãn a+b|ab và a+c|ac.
Chứng minh rằng gcd(a, b, c)>1.
Hướng dẫn giải sẽ có ở trang tiếp theo ...
www.MATHVN.com
www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ 5
Gợi ý giải bài số 1. Ta cần phân tích xem với hai số x, y nguyên dương mà x+y|xy có tính chất
gì đặc biệt. Đặt u= (x, y), ta viết x=ux1, y =uy1. Khi đó x1+y1|u(x1y1). Vì gcd(x1+y1, x1y1) = 1
nên x1+y1|u. Từ đây suy ra u > x1, y1. Do đó ta tìm được dạng tổng quát của các cặp số nguyên
dương (x, y)như thế đó là x=x1(x1+y1)t, y =y1(x1+y1)t, trong đó t, x1, y1nguyên dương và
(x1, y1) = 1.
Ta nên phát biểu rõ ràng lại những gì vừa làm được.
Bổ đề 1. 1. Điều kiện cần và đủ để hai số x, y nguyên dương thỏa mãn x+y|xy là x=
x1(x1+y1)t, y =y1(x1+y1)t, trong đó t, x1, y1nguyên dương và (x1, y1) = 1.
2. Nếu x, y nguyên dương và x+y|xy thì gcd(x, y)>√x, √y.
Quay lại bài toán, theo giả thiết (a, b)·(a, c)> a. Mặt khác a≥(a, b)·(a, c)
(a, b, c)>a
(a, b, c)(như trên
đã chỉ ra), suy ra (a, b, c)>1.✷
Sau đây là một bài toán hay
Bài tập 1.2. (Russia MO 1997) Tìm tất cả các bộ ba (a, b, c)nguyên dương thỏa mãn
a+b= (a, b)2
b+c= (b, c)2
c+a= (c, a)2.
Hướng dẫn giải sẽ có ở trang tiếp theo ...
www.MATHVN.com
www.MATHVN.com