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) 2
10
≡ 10
7
(mod 2003) - VMO 2004,
(b) 14 ≡ 45
2
(mod 2011) - VMO 2011,
(c) (2n + 1)
3
+ 5
3

dãy quen thuộc đó là . . .
Xem tiếp ở trang sau . . .
www.MATHVN.com
www.MATHVN.com
2
dãy Fibonacci, với F
0
= 0, F
1
= 1, và F
n+2
= F
n+1
+ F
n
. Theo đẳng thức Cessani
thì F
2
n+1
− F
n+2
F
n
= (−1)
n
. Do đó F
2
2k
+ 1 = F
2k+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 a
1
, . . . , a
n
không
đồng thời bằng không. Số nguyên d lớn nhất có tính chất d | a
i
với mọi i = 1, n được gọi là ước
chung lớn nhất của n số a
1
, . . . , a
n
. Ta kí hiệu gcd(a
1
, . . . , a
n
).
Định lý 1. (Berzout) Tồn tại các số nguyên không x
1
, . . . , x
n
sao cho
gcd(x
1
, . . . , x

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

i=1
x
i
a
i
= N vô 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ố N lớn nhất là N =
a
1
a
2
− a
1
− a
2
.
2. Bài toán có nghĩa khi n > 2: chẳng hạn N ≤ (n − 1)a
1
···a
n
.
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ì (a


a
n
− 1
a − 1
, a −1

= gcd (n, a −1) với mọi a > 1 và n nguyên dương.
6. Tính chất của dãy Mersen: gcd(a
m
− 1, a
n
− 1) = a
(m,n)
− 1 với a > 1 và 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













1
, x
1
y
1
) = 1
nên x
1
+ y
1
| u. Từ đây suy ra u > x
1
, y
1
. 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 = x
1
(x
1
+ y
1
)t, y = y
1
(x
1
+ y
1
)t, trong đó t, x
1
, y

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

2
⇒
d
(d, 2)
| x + y + z ⇒
d
(d, 2)
| x, y, z ⇒
d
(d, 2)
= 1.
Vậy d | 2. Do đó d = 2. Thay vào () cộng lại ta được (x, y) = (y, z) = (z, x). Từ (x, y, z) = 1 suy ra
(x, y) = (y, z) = (z, x) = 1. Vì vậy
x + y = y + z = z + x = 2 ⇒ x = y = z = 1.
Từ đó ta được a = b = c = 2 . ✷
Bài tập 1.3. Cho a, b, c, d là các số nguyên dương thỏa mãn ad = bc và a < b
√
3 < c
√
2 < d
√
6.
Chứng minh rằng a ≥ 1 +
√
6d
2
+ 1.
(Chọn đội tuyển Toán Chuyên SPHN 2006)
Hướng dẫn giải có ở trang tiếp theo . . .
www.MATHVN.com

2
Theo định lý bốn số, tồn tại x, y, z, t thỏa mãn a = xy, b = xz, d = tz, c = ty. Ta có
S = (xy)
2
+ 6(tz)
2
− 3(xz)
2
− 2(ty)
2
= (3z
2
− y
2
)(2t
2
− x
2
).
Để ý rằng 3z
2
> y
2
, 2t
2
> x
2
. Thành thử S là số nguyên dương. Vậy S ≥ 1. Từ đó suy ra
a
2

Cho m > 1, a là các số nguyên thỏa mãn (a, m) = 1. Xét dãy a
0
, a
1
, . . . , a
m
gồm m + 1 số nguyên
tố cùng nhau với m. Do đó tồn tại hai số i < j mà a
i
≡ a
j
(mod m). Do đó a
j−i
≡ 1 (mo d m). Tóm
tại, tồn tại số nguyên dương x sao cho a
x
≡ 1 (mo d m) .
Định nghĩa 2. Cho m > 1 là một số nguyên. Với mỗi số nguyên a mà (a, m) = 1 ta kí hiệu h là số
nguyên dương bé nhất x thỏa mãn tính chất: a
h
≡ 1 (mo d m). Kí hiệu ord
m
(a) := h.
Câu hỏi. Cho trước một số nguyên dương a và một modulo m > 1. Câu hỏi đặt ra là liệu có tồn
tại a nguyên để h là cấp của a theo modulo m?
Bài tập 1.4. Cho n là số nguyên dương. Hãy xác định cấp của
1. 3 theo modulo 2
n
.
2. 2 theo modulo 3

Dự đoán: với n ≥ 3 thì ord
2
n
(3) = 2
n−2
.
Chú ý rằng a
2
+ 1 là số chẵn không chia hết cho 4 với mọi số lẻ a. Với mọi số nguyên x > 2 ta
có
3
2
x−2
− 1 = (3 −1)
  
.
.
.2
1

3
2
0
+ 1

  
.
.
.2
2

x
.
Đặc biệt 2
n
| 3
2
n−3
− 1.
Ta còn phải chứng minh 2
n−2
là số nguyên dương bé nhất có tính chất 3
h
− 1
.
.
. 2
n
. Ta viết
h = 2
a
· b, với b là số lẻ. Chú ý rằng với b lẻ thì 3
b
≡ 3 (mod 8), ta có
3
h
− 1 =

3
b
− 1

.
.
.2
1
···

(3
b
)
2
a−3
+ 1

  
.
.
.2
1
.
www.MATHVN.com
www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ 9
Vậy 2
a+1
 3
h
− 1. Do đó 2
n−2
≤ 2
a

y
(mod m) khi và chỉ
khi h | x − y.
Hệ quả 1. Nếu p là số nguyên tố, p  a, và h = ord
p
(a) thì h | p − 1.
Đây là hệ quả trực tiếp của định lý Fermat bé và định lý 5 nói trên:
a
p−1
≡ 1 (mo d p) với mọi p nguyên tố và p  a.
Hệ quả 2. Nếu p là một số nguyên tố lẻ và p | a
2
n
+ 1, với n là số nguyên dương, thì p ≡ 1
(mod 2
n+1
).
Chứng minh. Gọi h = ord
p
(a) thì h | p −1. Mặt khác, p | a
2
n+1
−1 nên h | 2
n+1
. Vậy h = 2
m
. Nếu
m ≤ n, thì h | 2
n
, do đó a

là số nguyên tố, thì tồn tại x nguyên để x
2
≡ 2 (mod p). Từ p | F
n
suy ra p ≡ 1 (mod 2
n+1
), do đó
p ≡ 1 (mod 8). Vậy tồn tại x để x
2
≡ 2 (mod 8). Lũy thừa 2
n
cả hai vế ta được x
2
n+1
≡ 2
2
n
≡ −1
(mod ). Do đó p | x
2
n+1
+ 1. Áp dụng kết quả của hệ quả 2 một lần nữa, ta được p ≡ 1 (mod 2
n+2
).
✷
Nhận xét. Hai số Fermat khác nhau luôn nguyên tố cùng nhau, do đó tập các ước nguyên tố của
chúng khác nhau.
Hệ quả 3. Giả sử rằng a là số nguyên > 1, các số p, q nguyên thỏa mãn p |
a
q

2
+ b
2
là số chẵn.
Gợi ý chứng minh: (a) Chuyển về dạng đồng dư a
2
≡ −b
2
(mod p). Do vậy a
p−1
≡ (−1)
p−1
2
b
p−1
(mod p). Giả sử p  a, khi đó p  b. Theo định lý Fermat bé thì 1 ≡ (−1)
p−1
2
(mod p), mâu thuẫn.
(b) Đầu tiên ta cần bổ đề sau
Bổ đề 2. Nếu p ≡ 1 (mod 4) là một số nguyên tố thì

p − 1
2

!
2
≡ −1 (mo d p).
Chứng minh. Theo định lý Wilson, nếu p là một số nguyên tố thì (p − 1)! ≡ −1 (mod p). Chú ý
rằng p − k ≡ (−1) · k (mod p), nên

≡ −1 (mod 4) (ví dụ
lấy x =

p−1
2

!) Xét tập hợp S = {u + xv : 0 ≤ u, v ≤ K}. Ta có |S| = (K + 1)
2
> p nên theo nguyên
lý Dirichlet sẽ có hai phần tử trùng nhau modulo p. Do đó có u
i
, v
i
để
u
1
+ xv
1
≡ u
2
+ xv
2
(mod p) ⇒ (u
1
− u
2
)
2
≡ x
2

, 2017 là số nguyên tố dạng 4k + 1 và ta có 2017 = 9
2
+ 44
2
.
(c) coi như bài tập về nhà!!!. ✷
Bài tập 1.5. Cho n > 1, a là các số nguyên dương mà n | a
n
+1. Chứng minh rằng gcd(a +1, n) > 1.
Hướng dẫn giải có ở trang sau . . .
www.MATHVN.com
www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ 11
Bài giải. Vì n > 1 nên n luôn có ít nhất một ước nguyên tố, ta chọn p là ước nguyên tố bé nhất.
Khi đó gcd(p, n −1) = 1. Gọi h = ord
p
(a). Ta có p | a
n
+ 1 | a
2n
− 1 nên h | 2n. Lại có h | p − 1 nên
h | (2n, p −1) = (2, p − 1) = 1, 2. Nếu h = 1 thì p | a − 1, do đó a
n
+ 1 ≡ 2 (mod p). Suy ra p = 2.
Nhưng khi đó a là số lẻ nên gcd(a + 1, n) là số chẵn.
Nếu h = 2 thì p lẻ và từ p | a
2
− 1 suy ra p | a + 1. Khi đó p | gcd(a + 1, n). ✷
Nhận xét. Nếu p là số nguyên tố và n > 1 thỏa mãn n | (p − 1)
n

2
a
+ 1. Điều này gợi ý cho ta kết quả sau
Bổ đề 3. Nếu p | a
2
n
+ 1, với p là số nguyên tố lẻ, thì p ≡ 1 (mod 2
n+1
).
Áp dụng bổ đề ta được ngay p ≡ 1 (mod 2)
a+1
. Như vậy, mọi ước của n đều có dạng 2
a+1
k + 1.
Do tích của các số có dạng 2
a+1
k +1 cũng có dạng 2
a+1
k +1 nên n ≡ 1 (mod 2
a+1
). Suy ra b ≥ a + 1.
Đổi vai trò, suy ra a ≥ b + 1, mâu thuẫn.
1.3 Phương trình đồng dư bậc nhất và ứng dụng
Ta xét phương trình
ax ≡ b (mod m) (2)
với a, b, m là các số nguyên, trong đó m > 1.
Định lý 7. Phương trình (2) có nghiệm khi và chỉ khi gcd(a, m) | b.
Chứng minh. Nếu gcd(a, m) | b thì b = t · gcd(a, m). Theo định lý Berzout, tồn tại các số nguyên
u, v để gcd(a, m) = ua + vm. Suy ra b = (tu)a + (tv)m. Hay a(tu) ≡ b (mod m). Ngược lại, nếu tồn
tại x để ax ≡ b (mod m) thì ax = b + my. Suy ra b = ax − my

mãn p | a
2
n
+ b
2
n
. Khi đó p ≡ 1 (mo d 2
n+1
).
Chứng minh. Ta có p  b. Gọi b

thỏa mãn bb

≡ 1 (mo d p), ta có
0 ≡ b
2
n

a
2
n
+ b
2
n

≡ (ab

)
2
n

3
− b
3
= n
4
với n nguyên nào đó.
Bài tập 1.10. Chứng minh rằng với mỗi số nguyên dương lẻ n, thì mọi ước nguyên dương của số
7
2n
+ 5 ·7
n
+ 1 đều có dạng 4k + 1.
Bài tập 1.11. Chứng minh rằng không có số nguyên dương m, n nào mà
m
n
+
n + 1
m
= 4.
Bài tập 1.12. Tìm tất cả các cặp số nguyên không âm (x, y) thỏa mãn 33
x
+ 31 = 2
y
.
Bài tập 1.13. Chứng minh rằng phương trình
x
2011
− 1
x − 1
= y

| y
20
.
Bài tập 1.19. Cho m, n là các số nguyên dương thỏa mãn m
2
+ mn + n
2
| mn(m + n) và m > n.
Chứng minh rằng (m − n)
3
≥ 3mn.
Bài tập 1.20. Tìm n nguyên dương để
1. 3
n
| n
3
+ 1.
2. n
2
| 2
n
+ 1.
Bài tập 1.21. (Wolstenholme) Co p ≥ 5 là số nguyên tố. Ta viết
1
1
+
1
2
+ ···+
1