ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN THÚY HẰNG

HÀM SINH BỞI CÁC ƯỚC SỐ
VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN, NĂM 2015


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN THÚY HẰNG

HÀM SINH BỞI CÁC ƯỚC SỐ
VÀ ỨNG DỤNG

Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
Mã số: 60.46.01.13

LUẬN VĂN THẠC SĨ TOÁN HỌC

Người hướng dẫn khoa học:
PGS.TS NÔNG QUỐC CHINH

THÁI NGUYÊN, NĂM 2015


2.1.1 Định lí Ramanujan . . . . . . .
2.2 Số hoàn hảo và các số liên quan . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

14
14
19

3 Một số bài toán áp dụng
3.1 Tổng và hiệu của tích các cặp số . . . . . . . . . . . . . .
3.2 Tập các bội số của một tập hợp cho trước . . . . . . . .
3.3 Tập các số thừa . . . . . . . . . . . . . . . . . . . . . . .

24
24
34
38

Kết luận

45

Tài liệu tham khảo

46


1

Mở đầu

Một số kiến thức cơ bản của số học
Phép chia trong tập số nguyên

Định nghĩa 1.1. Cho hai số nguyên a và b , với b = 0 . Nếu có một số
nguyên q sao cho a = bq thì ta nói rằng b chia hết a hay a chia hết cho
.
b hoặc b là ước của a và ký hiệu là b | a hay a..b.
Tính chất 1.1.
1.

±1 | a với a ∈ Z.

2.

.
0..a với a ∈ Z, a = 0.

3.

.
a..a với a ∈ Z, a = 0.

4.

b | a và a | b khi và chỉ khi a = ±b.

5.

b | a và c | b kéo theo c | a.


a = bq + r,
a = bq1 + r1 ,

0 ≤ r < |b|,
0 ≤ r1 < |b|,

Khi đó ta được
bq + r = bq1 + r1 ⇒ r − r1 ≤ b(q − q1 ).
Nhưng |r − r1 | < |b|, cho nên |b||q − q1 | < |b|, nghĩa là |q − q1 | < 1. Hệ
thức này buộc q − q1 = 0 nghĩa là q = q1 , từ đó suy ra r = r1 (điều phải
chứng minh).
1.1.2

Ước số chung lớn nhất (ƯSCLN)

Định nghĩa 1.2. Cho hai số nguyên a, b trong đó ít nhất một số khác
0. Số dương d được gọi là ƯSCLN của a, b và được ký hiệu là d := (a, b)
nếu
1. d | a và d | b ( d là ước số chung của a và b).
2. Nếu c | a và c | b thì c | d.
Nói cách khác, d là ƯSCLN của hai số a và b nếu d là ước chung
của a và b đồng thời d là số lớn nhất trong các ước số chung của a
và b. Nếu (a, b) = 1 thì ta nói hai số a và b nguyên tố cùng nhau.
Nhận xét 1.1. Trong trường hợp a, b có một số bằng 0 thì hiển nhiên
ƯSCLN của chúng chính là số kia.
Tính chất 1.2.


4


0 < r1 < |b|

b = r1 q1 ,

0 < r2 < r1

r1 = r2 q2 + r3 ,

0 < r3 < r2

...

...

rn−2 = rn−1 qn−1 + rn ,

0 < rn < rn−1

rn−1 = rn qn .
Dãy phép chia có dư liên tiếp này được gọi là thuật toán Euclid thực hiện
trên hai số a, b. Dãy này phải là dãy hữu hạn và thuật toán Euclid phải
kết thúc với một số dư rn+1 = 0.
Theo chú ý ta có
(a, b) = (b, r1 ) = . . . = (rn−1 , rn ) = rn .


5

Như vậy, ƯSCLN của hai số a, b là số dư cuối cùng khác 0 trong thuật
toán Euclid thực hiện trên hai số a, b.


Định nghĩa 1.4. Hàm số học là hàm số có miền xác định là tập các số
nguyên dương và miền giá trị là tập các số phức.


6

Ví dụ 1.1.
a) Hàm d(n) đếm các ước khác nhau của một số tự nhiên n ≥ 1 là
hàm số học.
b) Hàm phi-Euler ϕ(n) là hàm số học.
1 nếu n = 1
c) Hàm δ : Z+ → C, δ(n) =
là hàm số học.
0 nếu n ≥ 2
d) Hàm O : Z+ → C, O(n) = 0 là hàm số học.
Định nghĩa 1.5. Một hàm số học f được gọi là hàm nhân tính nếu với
mọi cặp số m, n nguyên tố cùng nhau, ta có f (n.m) = f (n).f (m). Trong
từng trường hợp đẳng thức đúng với mọi m, n (không nhất thiết nguyên
tố cùng nhau) hàm f gọi là hàm nhân tính mạnh.
Ví dụ 1.2. Ta có
µ(1) = 1,
µ(8) = 0,

µ(6) = 1,
µ(4) = 0,

µ(2) = −1,

µ(7) = −1,

với ap là số nguyên thỏa mãn:
0 ≤ ap ≤ νp (n).


7

Vì mỗi số mũ ap có thể nhận vp (n) + 1 giá trịn khác nhau nên ta có
(νp (n) + 1).

d(n) =
p|n

Định lý 1.7. Hàm d(n) là hàm nhân tính.
Chứng minh.
Cho m và n là hai số nguyên tố cùng nhau,
pνp (m),

m=
p|m

và
q νq (n).

n=
q|n

Vì (m, n) = 1 nên tập hợp các số nguyên tố là ước của m và tập hợp các
số nguyên tố là ước của n là rời nhau. Vì vậy
pνp (m)


d(18) = d(21 .32 ) = (1 + 1)(2 + 1) = 6
d(19) = d(191 ) = 1 + 1 = 2
d(20) = d(22 .51 ) = (2 + 1)(1 + 1) = 6
d(21) = d(211 ) = 1 + 1 = 2.
Ví dụ 1.4. Chứng minh rằng n là số nguyên tố khi và chỉ khi d(n) = 2.
Lời giải.
• Nếu n là số nguyên tố thì n là một số tự nhiên lớn hơn 1 và không
có ước nào ngoài 1 và chính nó. Do đó d(n) = 2.
• Nếu d(n) = 2 thì số các ước số của số nguyên dương n là 2. Như
vậy n là một số nguyên tố.
Ví dụ 1.5. Chứng minh rằng d(n) là số nguyên tố khi và chỉ khi n = pq−1
với q và p là các số nguyên tố.
Lời giải.
• Nếu d(n) là số nguyên tố, giả sử là q. Khi đó ta có, d(n) = (q−1)+1.
Như vậy n = pq−1 với p là số nguyên tố.
• Nếu n = pq−1 với q và p là các số nguyên tố thì rõ ràng d(n) =
(q − 1) + 1 = q.
Như vậy d(n) là số nguyên tố.
Ta được điều phải chứng minh.
Ví dụ 1.6. Chứng minh rằng:
d = nd(n)/2 .
d|n

Lời giải.
• Giả sử n = pa với p là số nguyên tố, a là số nguyên dương. Ta có
các ước của pa là 1, p, p2 , . . . , pa . Do đó,
2

a


d = nd(n)/2 .
d|n

• Giả sử số nguyên dương n có phân tích ra thừa số nguyên tố
n = pa11 pa22 . . . pas s .
Khi đó
d=

a1 (a1 +1) a2 (a2 +1)
p1 2 p2 2

as (as +1)
. . . ps 2

= (pa11 pa22 . . . pas s )

(a1 +1)(a2 +1)...(as +1)
2

d|n

Mặt khác, d(n) = (a1 + 1)(a2 + 1) . . . (as + 1). Vì thế
n

d(n)
2

= (pa11 pa22 . . . pas s )

(a1 +1)(a2 +1)...(as +1)

kε

22

,

.


10

(vì d(pk ) = k + 1) nên bị chặn đối với k ≥ 1, và vì vậy
d(pk )
f (p ) =
pkε
k+1
=
pkε



k+1
1
=  kε   kε 
p2
p2
k+1
1
≤
ε

đếm các số của mạng (u, v) trong hình chữ nhật trên hyperbol uv = n
nằm trong góc phần tư u > 0 và v > 0. Hàm tổng D(x) đếm các số
lưới điểm trong góc phần tư ở dưới hoặc ở trên hyperbol uv = x và
1 ≤ v ≤ x/u. lưới điểm này có thể chia thành ba lớp rời nhau.
√
(i) 1 ≤ u ≤ x/u và 1 ≤ u ≤ x,
√
√
(ii) 1 ≤ u ≤ x và x ≤ v ≤ x/u,


11

(iii)

√

x ≤ u ≤ x và 1 ≤ v ≤ x/u.

Lớp thứ ba trên bao gồm các lưới điểm (u,v) thỏa mãn
√
√
1 ≤ v ≤ x và
x ≤ u ≤ x/u.
Ta suy ra
D(x) =

√

x


= 2x
√
1≤u≤ x

1
−2
u

√

1≤u≤ x

x
−
u

x
−
v

(x)

(x)

x
x
−
u
u

√
x
−x+O x
u

√

√
1
x+γ+O √
−x+O x
x
√
= x log x + (2γ − 1)x + O x .
= 2x log

Vậy suy ra điều phải chứng minh.
Định lý 1.10. Với x ≥ 1,
(log n − d(n) − 2γ) = O(x1/2 ).

∆(x) :=
n≤x

Chứng minh.
Theo định lí 1.9 ta có
d(n) = x log x + (2γ − 1)x + O

(x) .

n≤x

Cho (m, n) = 1. Với mỗi bậc của sự phân tích của mn thành l nhân
tử ta có thể xác định bậc của sự phân tích m và n thành l phần. Nếu
mn = d1 . . . dl là bậc của sự phân tích của mn thành l phần, với mỗi
i = 1, . . . l tồn tại duy nhất số nguyên ei và fi thỏa mãn ei chia hết cho
m và fi chia hết cho n và di = ei .fi . Vì vậy m = e1 . . . el và n = f1 . . . fl
là bậc của sự phân tích m và n phân biệt. Sự xây dựng này có thể nghịch
đảo vì vậy ta có thiết lập song ánh giữa bậc của sự phân tích mn và cặp
của bậc sự phân tích m và n. Ta suy ra rằng dl (m, n) = dl (m)dl (n), do
đó hàm dl là hàm nhân tính.
Một sự phân tích của lũy thừa số nguyên tố pa có thể viết một cách duy
nhất dưới dạng pa = pb1 pb2 . . . pbl với (b1 , . . . , bl ) là bậc của l – bộ các số
nguyên không âm thỏa mãn b1 + · · · + bl = a. Ta suy ra rằng dl (pa ) là số
bậc của sự phân chia a thành l phần không âm. Ta hình dung dãy của
a + l − 1 là các ô vuông màu đỏ. Nếu ta chọn l − 1 ô vuông màu xanh thì
còn lại a ô vuông màu đỏ có thể chia thành l dãy con (có thể rỗng) liên


13

tục của ô vuông màu đỏ, được tách bởi các ô vuông màu xanh. Mỗi bậc
của sự phân chia a thành l phần không âm có thể vẽ được trong phương
pháp này, vì vậy dl (pa ) là số các phương pháp để chọn l − 1 hình chữ
nhật từ tập hợp a + l − 1 hình chữ nhật, nghĩa là
a+l−1
.
l−1

dl (pa ) =
Vậy định lý đã được chứng minh.
Định lý 1.12. Với l ≥ 2,


=
d1 ...dl+1 ≤x

x
d1 . . . dl+1


=
d1 ...dl+1



x
+O
d
.
.
.
d
l+1
≤x 1
d

1

1 ...dl+1 ≤x

x logl x
=

n
.
δ2

Chứng minh.
Ta định nghĩa hàm số học µ
˜ như sau:
√
µ( n) nếu n là số chính phương,
µ
˜(n) =
0
trong các trường hợp còn lại.
Ta có µ
˜ là hàm nhân tính. Do tích chập Dirichle của các hàm nhân tính
là hàm nhân tính nên hàm số µ
˜ ∗ d4 là hàm nhân tính,và
µ
˜ ∗ d4 (n) =

µ
˜(d)d4

n
d

µ(δ)d4

n
.

3

= 4.

Nếu a ≥ 2 thì
µ
˜ ∗ d4 (pa ) =

µ
˜(δ)d4
δ 2 |pa

pa
δ2

= d4 (pa ) − d4 (pa−2 )
=

a+3
a+1
−
3
3

= (a + 1)2 .
Do d(pa ) = a + 1 ta suy ra được
d2 (pa ) = (a + 1)2 = µ
˜ ∗ d4 (pa ),
với mọi lũy thừa của số nguyên tố pa . Các hàm số d2 và µ
˜ ∗ d4 là các

µ(δ)d4
n≤x δ 2 |n

=

µ(δ)d4 (k)
δ 2 k≤x
√
δ≤ x

=
√
δ≤ x

=

k≤x/δ 2

µ(δ)D4

x
δ2

x
x
3 x
2 x
log
+
O


µ(δ)

=

x
6

√
δ≤ x

δ≤ x

Số hạng thứ nhất của tổng trên là
x
6

√
δ≤ x

x
µ(δ)
3 x
log
=
δ2
δ2
6

3

δ≤ x
δ≤ x


3
x 6
1
log δ 
3
x log2 x
√
+
O
log
x
+
O
=
6 π2
x
δ
√
δ≤ x

x log3 x
=
+ O(x log2 x).
2
π
Tương tự, ta có số hạng thứ hai là


σ(6) = 1 + 2 + 3 + 6 = 12

σ(2) = 1 + 2 = 3

σ(7) = 1 + 7 = 8

σ(3) = 1 + 3 = 4

σ(8) = 1 + 2 + 4 + 8 = 15

σ(4) = 1 + 2 + 4 = 7

σ(9) = 1 + 3 + 9 = 13

σ(5) = 1 + 5 = 6

σ(10) = 1 + 2 + 5 + 10 = 18.

Nếu n ≥ 2 thì σ(n) ≥ n + 1. Ta có thể sử dụng sự phân tích thành nhân
tử của n để tính σ(n). Ta bắt đầu với ví dụ sau.
Ví dụ. Xét 180 = 22 32 5. Mọi ước d của 180 đều có dạng d = 2a 3b 5c , với
0 ≤ a ≤ 2, 0 ≤ b ≤ 2 và o ≤ c ≤ 1. Ta có
σ(180) =

d
d|180

= 1 + 2 + 4 + 5 + 6 + 9 + 10 + 12 + 15 + 18
+ 20 + 30 + 36 + 45 + 60 + 90 + 180

.
p−1

Đây là công thức biểu diễn σ(n) của n.
Ví dụ 2.1. Tính σ(n) với 11 ≤ n ≤ 20.
Lời giải.
σ(11) =
σ(12) =
σ(13) =
σ(14) =
σ(15) =
σ(16) =
σ(17) =
σ(18) =
σ(19) =
σ(20) =

112 − 1
σ(11 ) =
= 12
11 − 1
23 − 1 32 − 1
2 1
.
= 7.4 = 28
σ(2 .3 ) =
1
3−1
132 − 1 168
1

.
= 3.13 = 39
σ(2 .3 ) =
1
2
192 − 1
1
σ(19 ) =
= 20
18
23 − 1 52 − 1
2 1
σ(2 .5 ) =
.
= 48.
1
4
1

Định lý 2.3. Hàm số học σ(n) là hàm nhân tính.
Chứng minh.
Giả sử m và n là hai số nguyên tố cùng nhau. Do không có số nguyên
tố nào là ước của cả m và n, ta có
σ(mn) =
p|mn

pνp (mn)+1 − 1
p−1



q = 2p − 1,
và
n = 2p−1 q.
Chứng minh.
Nếu n = 2p−1 q thì q là số lẻ và 2n = 2p q. Ta được
σ(n) = σ(2p−1 )σ(p)
= (2p − 1)(q + 1)
= 2p q + (2p − q − 1).
Vậy n là số hoàn hảo.
Ngược lại, nếu n là số hoàn hảo, σ(n) = 2n. Do n là số chẵn nên ta viết
n dưới dạng
n = 2k−1 m,


20

với m là số lẻ và k ≥ 2, ta có
2k m = 2n = σ(n) = σ(2k−1 )σ(m) = (2k−1 )σ(m).
Từ đó ta có 2k − 1 là ước của 2k m và 2k − 1 là số nguyên tố với 2k , áp
dụng bổ đề Euclide ta được 2k − 1 là ước m và vì vậy
m = (2k − 1)l,
đối với số nguyên lẻ l. Khi đó
2k (2k − 1)l = (2k − 1)σ (2k − 1)l .
Nếu l > 1 thì 1, l và (2k − 1)l là các ước khác nhau của (2k − 1)l, và
2k l = σ (2k − 1)l ≤ 1 + l + (2k − 1)l = 2k l + 1,
điều này vô lý. Vì vậy l = 1 và
2k = σ(2k − 1)l = 1 + (2k − 1) +

d.
d|(2k −1)l

σ ∗ (m) = n.
Như vậy cặp nguyên dương (m, n) là cặp thân mật nếu
σ(m) = σ(n) = m + n.
Ví dụ, cặp (220, 284) là cặp thân mật vì
σ ∗ (220) = 284,
và
σ ∗ (284) = 220.
Ta không biết được rằng có tồn tại vô hạn các cặp số thân mật hay không.

Ví dụ 2.2. Chứng minh rằng (9363584, 9437056) là cặp thân mật.
Lời giải.
Ta có
9363584 = 27 × 191 × 383,
nên
28 − 1 1912 − 1 3832 − 1
σ(9363584) =
×
×
1
190
382
= 18800640.
Suy ra
σ ∗ (9363584) = σ(9363584) − 9363584


22

= 9437056


σ ∗ (S1 (n)),

......
Sk+1 (n)

=

σ ∗ (Sk (n)),

với mọi số nguyên dương k. Dãy {Sk (n)}∞
k=0 được gọi là dãy các ước số
của n.
Từ sự tồn tại của số thừa, số hoàn hảo và số thiếu, ta thấy rằng
Sk+1 (n) > Sk (n), Sk+1 (n) = Sk (n) hoặc Sk+1 (n) < Sk (n) và vì vậy dãy
các ước số có thể dao động tăng hoặc giảm.
• Đối với các số nguyên dương n nhỏ, qua tính toán cụ thể người ta
luôn thấy phần tử sau của dãy là tuần hoàn. Chẳng hạn, dãy các
ước số của 12 là
12, 16, 15, 9, 4, 3, 1, 0, 0, . . .