1


Mục lục

MỞ ĐẦU

1

1 Kiến thức chuẩn bị
1.1 Tính chia hết . . . . . . . . . . . . .
1.2 Ước chung lớn nhất . . . . . . . . . .
1.3 Bội chung nhỏ nhất . . . . . . . . . .
1.4 Số nguyên tố . . . . . . . . . . . . . .
1.5 Đồng dư thức . . . . . . . . . . . . .
1.6 Hàm số số học và tính chất nhân . .
1.7 Hàm số Mơ-bi-us và luật thuận nghịch

.
.
.
.
.
.
.

2
2
2
4
4

5
5
7

.
.
.
.

10
10
14
17
20

2 Các
2.1
2.2
2.3
2.4

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
Đê-đê-kin-Liu-vin

hàm số học cơ bản

Phi - hàm Ơ-le . . . . . . . . . . . . .
Hàm tổng các ước số dương của n . . .
Hàm tổng các chữ số của số tự nhiên n
Hàm số các ước τ (n) . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.
.
.
.

.
.

.
.

.
.
.
.
.
.
.

.
.
.
.

3 Một số ứng dụng của các hàm số học
3.1

Ứng dụng của Phi - hàm Ơ-le . . . . . . . . . .
3.1.1 Xét đồng dư môđulô của một số nguyên
3.1.2 Chứng minh phép chia với dư . . . . . .
3.1.3 Giải phương trình đồng dư . . . . . . .
3.1.4 Tìm nghiệm nguyên của phương trình .

2

22
. .
tố

. .
. .
. .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.

.
.
.

.
.
.
.
.

22
22
23
24
25


3

3.1.5
3.1.6

Tìm cấp của số nguyên . . . . . . . . . . . . . . . . .
Tìm số tự nhiên thỏa mãn tính chất hàm số ϕ(n) . .

26
27

3.2


Ứng dụng của hàm tổng các ước số dương của số tự nhiên n
3.2.1 Chứng minh một số là hợp số . . . . . . . . . . . . .
3.2.2 Chứng minh một số là số hoàn hảo . . . . . . . . . .
3.2.3 Chứng minh bất đẳng thức liên quan tới σ(n) . . . .

.
.
.
.

29
29
30
33

3.3

Ứng dụng của hàm S(n) . . . . . . . . . . . . . . . . . .
3.3.1 Tìm n bởi S(n) thỏa mãn một hệ thức cho trước
3.3.2 Tính giá trị S(n) . . . . . . . . . . . . . . . . .
3.3.3 Chứng minh một số biểu thức liên quan tới S(n)
3.3.4 Xét tính bị chặn của hàm số chứa S(n) . . . . . .

.
.
.
.
.

36

36
38
39
41

3.4

Ứng dụng của hàm số các ước τ (n) . . . . . . . . . . . . . .
3.4.1 Tìm n thỏa mãn một điều kiện cho trước của τ (n) . .
3.4.2 Một số bất đẳng thức liên quan tới hàm τ (n) . . . . .
3.4.3 Tìm số nghiệm của phương trình bằng phương pháp sử
dụng τ (n) . . . . . . . . . . . . . . . . . . . . . . . .

42
42
45

Ứng dụng của hàm phần nguyên [x] . . . . . . . . . . . . . .
3.5.1 Bài toán định tính . . . . . . . . . . . . . . . . . . . .
3.5.2 Bài toán định lượng . . . . . . . . . . . . . . . . . . .

48
48
50

3.5

.
.
.

.
.

.
.
.
.
.

47

KẾT LUẬN

52

Tài liệu tham khảo

52


MỞ ĐẦU
Hàm số số học và ứng dụng có nhiều ứng dụng quan trọng trong đại số
hiện đại. Trong những năm gần đây, đây là một trong nhiều vấn đề được
nhiều người quan tâm, chú ý và thích thú nghiên cứu. Với mục đích tìm
hiểu, nghiên cứu nhằm làm rõ hơn về vấn đề này, em đã chọn luận văn của
mình là: "Hàm số số học và ứng dụng". Luận văn của em gồm 3 chương:
Chương 1: Là các kiến thức chuẩn bị, chương này đề cập đến các khái niệm
và tính chất có liên quan đến các hàm số học cơ bản. Đây là các kiến thức
nền tảng cho chương 2 và chương 3
Chương 2: Trong chương này ta sẽ tìm hiểu về một số hàm số học cơ bản và

tính chất của nó.
Chương 3: Trong chương này ta xét một số ứng dụng của các hàm số học
trong việc giải phương trình, tìm nghiệm nguyên hay chứng minh một số
bài toán đại số .

1


Chương 1

Kiến thức chuẩn bị
1.1

Tính chia hết

Số nguyên a được gọi là chia hết cho số nguyên b, b = 0, nếu a = bq với số
.
nguyên q nào đó. Khi đó ta nói a là bội của b và kí hiệu a..b.
Ta còn nói b chia hết a hay b là ước của a và kí hiệu b | a.
Phép chia với dư. Với cặp số nguyên a và b, b = 0 tồn tại cặp số nguyên q , r
duy nhất sao cho

a = bq + r, 0 ≤ r < |b|.
Khi đó ta nói rằng a chia hết cho b được thương q và dư r. Số q được gọi là
thương hụt nếu r = 0.

1.2

Ước chung lớn nhất


Số nguyên d được gọi là ước chung của các số nguyên a1 , a2 , .., an nếu nó là
ước của mỗi số đó.
Ước chung d của các số nguyên a1 , a2 , ..., an được gọi là ước chung lớn nhất
(ƯCLN) nếu d là bội của mọi ước chung của a1 , a2 , ..., an . Theo định nghĩa
các ƯCLN của các số a1 , a2 , ..., an phải chia hết lẫn nhau ,do đó chún chỉ
khác nhau bởi dấu.Trong hai số ±d cùng là ƯCLN của các số a1 , a2 , ..., an
số dương thường được kí hiệu là d = CLN (a1 , a2 , .., an ) hoặc

d = (a1 , a2 , ..., an ).
2


Một số tính chất đáng lưu ý của ƯCLN:
- Tập hợp các ước chung của a1 , a2 , ..., an trùng với tập hợp các ước của
ƯCLN của các số đó.
- Nếu d là một ƯCLN của các số a1 , a2 , ..., an thì tồn tại các số nguyên
x1 , x2 , ..., xn sao cho

d = x1 a1 + x2 a2 + ... + xn an .
Đặc biệt, (a1 , a2 , ..., an ) = 1 khi và chỉ khi tồn tại các số nguyên
x1 , x2 , ..., xn sao cho

1 = x1 a1 + x2 a2 + ... + xn an .
Trong trường hợp này các số a1 , a2 , ..., an được gọi là nguyên tố cùng nhau.
Để tìm ƯCLN của hai số ta thường sử dụng tính chất sau:

a = bq + r ⇒ (a, b) = (b, r)
( lưu ý rằng ở đây không đòi hỏi 0 < r < |b|).
Đặc biệt ta có thuật toán Ơclit để tìm ƯCLN của hai số nguyên:
Nếu


a = bq0 + r1 , 0 < r1 < b
b = r1 q1 + r2 , 0 < r2 < r1
....
rn−2 = rn−1 qn−1 + rn , 0 < rn < rn−1
rn−1 = rn qn .
thì (a, b) = rn , nghĩa là ƯCLN của a, b bằng số dư cuối cùng rn trong thuật
toán nói trên.
ƯCLN của nhiều số được tính theo công thức

(a1 , a2 , ..., an ) = ((a1 , a2 , ..., an−1 ), an ).

3


1.3

Bội chung nhỏ nhất

Số nguyên m được gọi là bội chung của các số nguyên a1 , a2 , ..., an nếu nó
chia hết cho mỗi số nguyên đó.
Bội chung m của các số nguyên a1 , a2 , ..., an được gọi là bội chung nhỏ nhất
của các số này ( viết tắt là BCNN) nếu nó là ước của mọi bội chung của
a1 , a2 , ..., an .
Nếu m và m’ là BCNN của các số a1 , a2 , ..., an thì m = ±m . Trong trương
hợp m > 0 ta kí hiệu:

m = BCN N (a1 , a2 , ..., an ), hoặc m = [a1 , a2 , ..., an ]
và quy ước gọi nó là BCNN của a1 , a2 , ..., an .
Để tìm bội chung nhỏ nhất của hai số ta thường sử dụng công thức


[a, b] =

ab
.
(a, b)

Bội chung nhỏ nhất của nhiều số được tính theo công thức

[a1 , a2 , ..., an ] = [[a1 , a2 , ..., an−1 ], an ].
Trong nhiều trường hợp BCNN của nhiều số còn được xác định nhờ tính
chất sau
m
m m
m = [a1 , a2 , ..., an ] ⇔ ( , , ..., ) = 1.
a1 a2
an

1.4

Số nguyên tố

Số tự nhiên lớn hơn 1 không có ước nào khác ngoài 1 và chính nó được gọi
là số nguyên tố.
Những tính chất cơ bản thường gặp của số nguyên tố:
- Cho p là số nguyên tố. Khi đó với mọi số nguyên a thì hoặc a chia hết cho
p hoặc a nguyên tố cùng nhau với a.
- Nếu tích ab của hai số tự nhiên chia hết cho số nguyên tố p thì hoặc a chia
hết cho p hoặc b chia hết cho p.


4


Định lí cơ bản. Mỗi số tự nhiên lớn hơn 1 đều phân tích được thành những
thừa số nguyên tố và sự phân tích đó là duy nhất nếu không kể đến thứ tự
của các thừa số.
Sự phân tích

a = pα1 1 pα2 2 ...pαk k
trong đó p1 , p2 , ..., pk là những số nguyên tố khác nhau, α1 , α2 , ..., αk là
những số nguyên dương, gọi là sự phân tích tiêu chuẩn của a.

1.5

Đồng dư thức

Cho số nguyên dương m. Hai số nguyên a và b được gọi là đồng dư với nhau
theo modul m nếu chúng có cùng số dư trong phép chia cho m, và kí hiệu bởi

a ≡ b (mod m).
Định nghĩa trên là tương đương với một trong hai phát biểu sau:
1. m |( a - b)
2. Tồn tại số nguyên t sao cho a = b + mt.
Khi thực hiện các phép toán trên đồng dư thức ta thường sử dụng hai tính
chất cơ bản sau:
1. Có thể cộng hoặc trừ từng vế nhiều đồng dư thức theo cùng một môđul
với nhau.
2. Có thể nhân từng vế nhiều đồng dư thức theo cung một môđul với nhau.

1.6


Hàm số số học và tính chất nhân

Định nghĩa 1.6.1. (i) Hàm số số học là một ánh xạ f: N ∗ → R từ tập các
số tự nhiên khác không N đến tập các số thực R.
(ii) Hàm số số học f: N ∗ → R được gọi là hàm số có tính chất nhân (hàm
nhân tính) nếu:
(i) f = 0, nghĩa là tồn tại số tự nhiên n0 ∈ N ∗ sao cho f (n0 ) = 0;
(ii) Với mọi m, n ∈ N ∗ , UCLN(m, n) = 1, ta nói f (mn) = f (m)f (n).
5


Trong trường hợp tính chất (ii) được thỏa mãn với mọi cặp số tự nhiên m, n
khác 0 thì ta có f là hàm có tính chất nhân hoàn toàn ( hàm hoàn toàn nhân
tính).
Ví dụ 1.6.2. Hàm số f: N ∗ → R xác định bởi f (n) = ns , với s ∈ Z là hàm
số số học hoàn toàn nhân tính.
Mệnh đề 1.6.3. Nếu f: N ∗ → R là hàm số có tính chất nhân thì f (1) = 1.
Chứng minh. Vì f có tính chất nhân nên theo định nghĩa tồn tại n0 ∈ N ∗
sao cho f (n0 ) = 0. Vì ƯCLN(n0 , 1) = 1 nên f (n0 ) = f (1.n0 ) = f (1).f (n0 ).
Suy ra f (1) = 1.
Mệnh đề 1.6.4. f1 : N ∗ → R và f2 : N ∗ → R là hai hàm số có tính chất
nhân thì hàm số f = f1 .f2 :N ∗ → R xác định bởi f (n) = f1 (n).f2 (n) cũng là
hàm số có tính chất nhân.
Chứng minh. Theo định nghĩa hàm f = f1 .f2 xác định với mọi n ∈ N ∗ .
Ngoài ra f (1) = f1 (1).f2 (1) = 1.1 = 1 nên f = 0.
Mặt khác giả sử n1 , n2 ∈ N ∗ sao cho ƯCLN(n1 , n2 ) = 1. Khi ấy ta có

f (n1 .n2 ) = f1 (n1 .n2 ).f2 (n1 .n2 ) = f1 (n1 )f1 (n2 )f2 (n1 )f2 (n2 )
= f1 (n1 )f2 (n1 )f1 (n2 )f2 (n2 ) = f (n1 )f (n2 ).

Vậy f là hàm có tính chất nhân.
Mệnh đề 1.6.5. Cho n = pα1 1 .pα2 2 ...pαk k là dạng phân tích tiêu chuẩn của số
tự nhiên n > 1 và f là một hàm số có tính chất nhân. Khi ấy ta có
k

(1 + f (pi ) + ... + f (pαi i )). (1)

f (d) =
d|n

(Tổng

d|n f (d)

i=1

gọi là tổng trải trên các ước của n).

Chứng minh. Khai triển vế phải của (1) ta có
k

f (pβ1 1 )f (pβ2 2 )...f (pβk k ).

(1 + f (pi ) + ... + f (pαi 1 )) =
0≤βi ≤αi

i=1

i=1,2,...,k


6


Ta chú ý rằng pβ1 1 , pβ2 2 , ..., pβk k là các số nguyên tố cùng nhau từng đôi một và
f là một hàm số có tính chất nhân, suy ra

f (pβ1 1 )f (pβ2 2 )...f (pβk k ) = f (pβ1 1 pβ2 2 ...pβk k ).
Từ đó

k

f (pβ1 1 pβ2 2 ...pβk k ).

(1 + f (p1 ) + ... + f (pαi i )) =
0≤βi ≤αi

i=1

i=1,1,...,k

Theo dấu hiệu về ước của n thì pβ1 1 pβ2 2 ...pβk k chạy qua tất cả các ước của n khi
βi chạy qua các giá trị 0, 1, 2, ..., αi với mọi i = 1, 2, ..., k nên cuối cùng ta
được
k

(1 + f (pi ) + ... + f (pαi i )) =
i=1

1.7


f (d).
d|n

Hàm số Mơ-bi-us và luật thuận nghịch Đê-đê-kin-Liu-vin

Định nghĩa 1.7.1. Hàm Mơ-bi-us µ: N ∗ → Z được xác định bởi công thức:



1 nếu n = 1;




µ(n) = 0 nếu n...p2 , với p là số nguyên tố;





(−1)k nếu n = p p ...p là tích của k số nguyên tố khác nhau.
1 2
k
Ví dụ.µ(2) = −1; µ(12) = 0; µ(15) = 1; µ(30) = −1.
Mệnh đề 1.7.2. Hàm Mơ-bi-us là hàm có tính chất nhân.
Chứng minh. Rõ ràng µ = 0, ta còn phải chứng minh ∀m, n ∈ N ∗ ,
UCLN(m, n) = 1 thì µ(mn) = µ(m)µ(n).
Thật vậy, khi m = 1 hoặc n = 1 thì đẳng thức là hiển nhiên. Thêm nữa
khi m hoặc n có nhân tử bình phương khác 1 thì tích mn cũng có nhân tử
bình phương khác 1 nên đẳng thức cũng là hiển nhiên. Trong trường hợp

còn lại giả sử m = p1 p2 ...pr và n = q1 q2 ...qs , ở đó p1 , p2 , ..., pr , q1 , q2 , ..., qs
7


là các số nguyên tố đôi một phân biệt ( vì UCLN(m, n) = 1). Khi ấy
mn = p1 p2 ...pr q1 q2 ...qs nên ta có µ(mn) = (−1)r+s = (−1)r .(−1)s =
µ(m)µ(n).
Mệnh đề 1.7.3. Cho f là một hàm có tính chất nhân và n = pα1 1 pα2 2 ...pαk k là
dạng phân tích tiêu chuẩn của n ∈ N ∗ . Khi ấy ta có
k

(1 − f (pi )).

µ(d)f (d) =
i=1

d|n

Chứng minh. Ta có µ và f là hai hàm có tính chất nhân nên tích của chúng
cũng là hàm có tính chất nhân. Sử dụng công thức tính tổng trải trên các
ước của n đối với hàm g = µ.f ta được

g(d) =
d|n

µ(d)f (d)
d|n
k

(1 + µ(pi )f (pi ) + µ(p2i )f (p2i ) + ... + µ(pα1 1 )f (pαi i ))


=
i=1
k

(1 − f (pi )).

=
1

( Vì µ(pi ) = −1, µ(ps ) = 0, ∀s ≥ 2.)
Hệ quả 1.7.4.

µ(d) =

i)
d|n

ii)
d|n




0 nếu n > 1


1 nếu n = 1




 ki=1 (1 − 1 ) nếu n = pα1 1 pα2 2 ...pαk
k
pi

µ(d)
=

d

1 nếu n = 1

Chứng minh. (i) Thật vậy, áp dụng tính chất trên với f là hàm số xác định
bởi f (n) = 1, ∀n ∈ N ∗ .
(ii) Thật vậy, kết quả này suy ra từ việc áp dụng tính chất trên với f là hàm
số xác định bởi f (n) = n1 , ∀n ∈ N ∗ .
8


Mệnh đề 1.7.5. Giả sử f là một hàm số số học, g là hàm số số học xác định
bởi g(n) = d|n f (d). Ta có

f (n) =
d|n

Chứng minh. Ta tính tổng
g(n). Ta có
n
µ(d)g( ) =
d

d|n

n
µ(d)g( ).
d

n
d|n µ(d)g( d )

µ(d)
d|n

dựa vào định nghĩa của hàm số

f (d ) =
d

| nd

µ(d)f (d ).
d|n d

| nd

Ta thấy d | nd nên tồn tại c ∈ N ∗ sao cho cd = nd hay cd = dn . Điều đó tương
đương với d| dn . Như vậy vai trò của d và d như nhau cho nên trong biểu thức
đang xét có thể thay đổi thứ tự lấy tổng giữa d và d mà không làm thay đổi
giá trị lấy tổng ta được
n
µ(d)g( ) =

µ(d)f (d ) =
µ(d)f (d )
d
n
n
d|n,d | d

d|n

=

f (d )
d |n

(Vì

d| dn

µ(d) = 0 nếu

n
d

d |n,d| d

> 1 và

µ(d) = f (n)
d| dn
d| dn


Vậy

f (n) =
d|n

9

µ(d) = 1 nếu
n
µ(d)g( ).
d

n
d

= 1).


Chương 2

Các hàm số học cơ bản
2.1

Phi - hàm Ơ-le

Định nghĩa 2.1.1. Giả sử n là một số nguyên dương. Phi - hàm Ơ-le của n
là số các số nguyên dương không vượt quá n và nguyên tố cùng nhau với n.
Kí hiệu Phi - hàm Ơ-le là ϕ(n)
Ví dụ 2.1.2. ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2, ϕ(4) = 2, ϕ(5) = 4.

Định nghĩa 2.1.3. Cho n là một số nguyên dương. Nếu a là số nguyên với
(a, n) = 1 thì luôn tồn tại số nguyên dương k để ak ≡ 1 (mod n). Số nguyên
dương k bé nhất thỏa mãn ak ≡ 1 (mod n) được gọi là cấp của số nguyên
a (mod n).
Định nghĩa 2.1.4. Một hệ thặng dư thu gọn môđul n là một tập hợp gồm
ϕ(n) số nguyên sao cho mỗi phần tử của tập hợp đều nguyên tố cùng nhau
với n và không có hai phần tử khác nhau nào đồng dư môđul n.
Ví dụ 2.1.5. Tập hợp {1, 3, 5, 7} là một hệ thặng dư thu gọn môđul 8. Tập
hợp {−3, −1, 1, 3} cũng vậy.
Định nghĩa 2.1.6. Một tập hợp A nào đó được gọi là một hệ thặng dư đầy
đủ (mod n) nếu với bất kì số x ∈ Z tồn tại một a ∈ A để x ≡ a (mod n)
Ví dụ 2.1.7. A = {0, 1, 2, ..., n − 1} là một hệ thặng dư đầy đủ theo modul n
Chú ý 2.1.8. Dễ thấy một tập hợp A = {a1 , a2 , ..., an } gồm n số sẽ là một
hệ thặng dư đầy đủ theo modul n khi và chỉ khi ai ≡ aj (mod n) với i = j và
i, j ∈ {1, 2, ..., n}.
10


Mệnh đề 2.1.9. Giả sử {r1 , r2 , ..., rϕ(n)} là một hệ thặng dư thu gọn môđul
n, a là số nguyên dương và (a, n) = 1. Khi đó, tập hợp {ar1 , ar2 , ..., arϕ (n)}
cũng là một hệ thặng dư thu gọn môđuln.
Chứng minh. Trước tiên ta chứng tỏ rằng, mỗi số nguyên arj là nguyên tố
cùng nhau với n. Giả sử ngược lại, (arj , n) > 1 với j nào đó. Khi tồn tại ước
nguyên tố p của (arj , n). Do đó, hoặc p|a, hoặc p|rj , tức là hoặc p|a và p|n,
hoặc p|rj và p|n. Tuy nhiên, không thể có p|rj và p|n vì rj và n là nguyên tố
cùng nhau. Tương tự, không thể có p|a và p|n. Vậy, arj và n nguyên tố cùng
nhau với mọi j = 1, 2, ..., ϕn.
Còn phải chứng tỏ hai số arj , ark (j = k) tùy ý không đồng dư modul n. Gỉa
sử arj ≡ ark (mod n), j = k và 1 ≤ j ≤ ϕ(n); 1 ≤ k ≤ ϕ(n). Vì (a, n) = 1
nên ta suy ra rj ≡ rk (mod n). Điều này mâu thuẫn vì rj , rk cùng thuộc

một hệ thặng dư thu gọn ban đầu modul n.
Ví dụ 2.1.10. Tập hợp {1, 3, 5, 7} là một hệ thặng dư thu gọn modul 8. Do
(3, 8) = 1 nên {3, 9, 5, 21} cũng là một hệ thặng dư modul 8.
Mệnh đề 2.1.11 (Định lí Ơ-le). Giả sử m là số nguyên dương và a là số
nguyên với (a, m) = 1. Khi đó aϕ(m) ≡ 1 (mod m).
Chứng minh. Giả sử {r1 , r2 , ..., rϕ(n) } là một hệ thặng dư thu gọn gồm các
số nguyên dương không vượt quá m và nguyên tố cùng nhau với m. Do
tính chất 1 và do (a, m) = 1, tập hợp {ar1 , ar2 , ..., arϕ(n) } cũng là một
hệ thặng dư thu gọn modul m. Như vậy, các thặng dư dương bé nhất của
ar1 , ar2 , ..., arϕ(m) phải là các số nguyên r1 , r2 , ..., rϕ(m) xếp theo thứ tự nào
đó. Vì thế nếu ta nhân các vế từ trong hệ thặng dư thu gọn trên đây, ta được:
ar1 .ar2 ...arϕ(m) ≡ r1 .r2 ...rϕ(m) (mod m).
Do đó, aϕ(m) .r1 .r2 ...rϕ(m) ≡ r1 .r2 ...rϕ(m) (mod m).
Vì (r1 , r2 , ..., rϕ(m) ) = 1 nên aϕ(m) ≡ 1(mod m).
Ta có thể tìm nghịch đảo môđul n bằng cách sử dụng định lí Ơ-le. Giả sử
a,m là các số nguyên tố cùng nhau, khi đó:

a.aϕ(m)−1 = aϕ(m) ≡ 1(mod m).
Vậy aϕ(m)−1 là nghịch đảo của a môđul m.

11


Ví dụ 2.1.12. 2ϕ(9)−1 = 26−1 = 25 = 32 ≡ 5(mod 9) là một nghịch đảo của
2 modul 9.
Hệ quả 2.1.13. (i) (a, b) = 1 thì aϕ(b) + bϕ(a) ≡ 1 (mod ab).
(ii) Với (a, b) = 1 và n, v là các số nguyên dương nào đó thì

anϕ(b) + bvϕ(a) ≡ 1 (mod ab).
(iii) Giả sử có k (k ≥ 2) số nguyên dương m1 , m2 , .., mk và chúng nguyên tố

với nhau từng đôi một. Đặt M = m1 .m2 ...mk = mi .ti ) với i = 1, 2, ..., k ta
có:

tn1 + tn2 + ... + tnk ≡ (t1 + t2 + ... + tk )n (mod M )n nguyên dương.
Bây giờ ta sẽ cho công thức tính giá trị của Phi - hàm Ơ -le tại n khi biết
phân tích của n ra thừa số nguyên tố.
Mệnh đề 2.1.14. Với số nguyên tố p ta có ϕ(p) = p − 1. Ngược lại nếu p là
số nguyên dương sao cho ϕ(p) = p − 1 thì p là số nguyên tố.
Chứng minh. Nếu p là số nguyên tố thì với mọi số nguyên dương nhỏ hơn p
đều nguyên tố cùng nhau với p. Do có p − 1 số nguyên dương như vậy nên
ϕ(p) = p − 1.
Ngược lại, nếu p là hợp số thì p có các ước d, 1 < d < p. Tất nhiên p và
d không nguyên tố cùng nhau. Như vậy, trong các số 1, 2, ..., p − 1 phải số
những số không nguyên tố cùng nhau với p, nên ϕ(p) ≤ p − 2 . Theo giả
thiết, ϕ(p) = p − 1. Vậy p là số nguyên tố.
Mệnh đề 2.1.15. Giả sử p là số nguyên tố và p là số nguyên dương. Khi đó:

ϕ(pa ) = pa − pa−1 .
Chứng minh. Các số nguyên dương nhỏ hơn pa không nguyên tố cùng nhau
với p là các số không vượt quá pa−1 và chia hết cho a. Có đúng pa−1 số như
vậy. Do đó tồn tại pa − pa−1 số nguyên nhỏ hơn pa và nguyên tố cùng nhau
với pa . Vậy, ϕ(pa ) = pa − pa−1 .
Ví dụ 2.1.16. ϕ(125) = ϕ(53 ) = 53 − 52 = 100; ϕ(210 ) = 210 − 29 = 525.
Tính chất 2.1.17. Nếu m,nlà các số nguyên dương nguyên tố cùng nhau thì
ϕ(mn) = ϕ(m).ϕ(n).
12


Chứng minh. Ta viết các số nguyên dương không vượt quá mn thành bảng
sau:

1 m + 1 2m + 1 ... (n − 1)m + 1

2 m + 2 2m + 2 ... (n − 1)m + 2
3 m + 3 2m + 3 ... (n − 1)m + 3
...

...

...

...

...

m

2m

3m

...

mn

Bây giờ giả sử r là một số nguyên không vượt quá m. Giả sử (m, n) = d > 1.
Khi đó, không còn số nào trong dòng thứ r nguyên tố cùng nhau với mn,
vì mỗi phần tử của dòng đó đều có dạng km + r, trong đó 1 ≤ k ≤ n − 1,
d| (km + r), vì d | m, d | r.
Vậy, để tìm các số trong bảng mà nguyên tố cùng nhau với mn, ta chỉ cần
xem các dòng thứ r với (m, n) = 1. Ta xét một dòng như vậy, nó chứa các số

r, m + r, ..., (n − 1)m + r. Vì (r, m) = 1 nên mỗi số nguyên trong dòng đều
nguyên tố cùng nhau với n. Như vậy, n số nguyên trong dòng lập thành hệ
thặng dư đầy đủ môđul n. Do đó có đúng ϕ(n) số trong hàng đó nguyên tố
cùng nhau với n. Do các sô đó cũng nguyên tố cùng nhau với m nên chúng
nguyên tố cùng nhau với mn.
Vì có ϕ(m) dòng, mỗi dòng chứa ϕ(n) số nguyên tố cùng nhau với mn nên
ta suy ra ϕ(mn) = ϕ(m)ϕ(n).
Kết hợp hai tính chất trên, ta được tính chất sau:
Định lý 2.1.18. Giả sử n = pn1 1 pn2 2 ...pnk k là phân tích n ra thừa số nguyên
tố. Khi đó:
1
1
1
ϕ(n) = n(1 − )(1 − )...(1 − ).
p1
p2
pk
Chứng minh. Vì ϕ là hàm có tính chất nhân nên nếu có phân tích như trên,
a
a
a −1
ta được: ϕ(n) = ϕ(pa11 )ϕ(pa22 )...ϕ(pakk ).Mặt khác: ϕ(pj j ) = pj j − pj j
=
aj
1
pj (1 − pj ), j = 1, 2, ..., k .

13



Vậy

1 a2
1
1
)p2 (1 − )...pakk (1 − )
p1
p2
pk
1
1
1
= pa11 pa22 ...pakk (1 − )(1 − )...(1 − )
p1
p2
pk
1
1
1
= n(1 − )(1 − )...(1 − ).
p1
p2
pk

ϕ(n) = pa11 (1 −

Mệnh đề 2.1.19. Giả sử n là một số nguyên dương. Khi đó:

ϕ(d) = n.
d|n


Chứng minh. Tổng trên đây được lấy theo các ước số của n. Ta phân chia
tập hợp các số tự nhiên từ 1 đến n thành các lớp sau đây. Lớp Cd gồm các số
nguyên m, 1 ≤ m ≤ n, mà (m, n) = d. Như vậy m thuộc Cd nếu và chỉ nếu
d là ước chung của m, n và (m/d, n/d) = 1. Như vậy, số phần tử của Cd là
các số nguyên dương không vượt quá n/d và nguyên tố cùng nhau với n/d;
tức là Cd gồm ϕ(n/d) phần tử. Vì mỗi số nguyên m từ 1 đến n thuộc một
và chỉ một lớp Cd nào đó d = (m, n) nên n bằng tổng của số các thành phần
trong các lớp Cd , d là ước số của n. Ta có n = d|n ϕ( nd ).

2.2

Hàm tổng các ước số dương của n

Định nghĩa 2.2.1. Hàm tổng các ước dương của số tự nhiên n được kí hiệu
là σ(n).
Ví dụ 2.2.2. σ(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28.
Chú ý 2.2.3. Ta có thể biểu diễn hàm σ(n) dưới dạng : σ(n) =
Mệnh đề 2.2.4. Giả sử m,n là
Khi đó, nếu d là ước chung của
d1 của m và d2 của n sao cho d
dương tương ứng của m và n thì

d|n d

các số nguyên dương nguyên tố cùng nhau.
mn thì tồn tại cặp duy nhất các ước dương
= d1 .d2 . Ngược lại, nếu d1 và d2 là các ước
d = d1 .d2 là ước dương của mn.


14


Chứng minh. Giả sử m, n có phân tích ra thừa số nguyên tố như sau:
n1 n2
nt
ms
1 m2
m = pm
1 p2 ...ps ; n = q1 q2 ...qt .

Vì (m, n) = 1 nên tập hợp số nguyên tố p1 , p2 , ..., ps và tập hợp các sô nguyên
tố q1 , q2 , ..., qt không có phần tử chung. Do đó phân tích ra thừa sô của mn
nt
ms n1 n2
1 m2
có dạng: mn = pm
1 p2 ...ps .q1 q2 ...qt .
Như vậy, nếu d là một ước chung của mn thì d = pe11 pe22 ...pess .q1f1 q2f2 ...qtft , trong
đó 0 ≤ ei ≤ mi (i = 1, 2, ..., s); 0 ≤ fi ≤ ni (i = 1, 2, .., t).
Đặt: d1 = pe11 pe22 ...pess , d2 = q1f1 q2f2 ...qtft . Rõ ràng d = d1 d2 và (d1 , d2 ) = 1.
Ngược lại, giả sử d1 và d2 là các ước dương tương ứng của m và n. Khi đó:

d1 = pe11 pe22 ...pses trong đó, 0 ≤ ei ≤ mi (i = 1, 2, ..., s)
d2 = q1f1 q2f2 ...qtft trong đó, 0 ≤ fi ≤ ni (i = 1, 2, ..., t).
Số nguyên d = d1 d2 = pe11 pe22 ...pess .q1f1 q2f2 ...qtft .
nt
ms n1 n2
1 m2
Rõ ràng là ước của mn = pm

1 p2 ...ps .q1 q2 ...qt vì lũy thừa của mỗi số
nguyên tố xuất hiện trong phân tích ra thừa số nguyên tố của d bé hơn hoặc
bằng lũy thừa của số nguyên tố đó trong phân tích của mn.
Bổ đề 2.2.5. Giả sử p là số nguyên t, a là số nguyên dương. Khi đó:

σ(pa ) = (1 + p + p2 + ... + pa ) =

pa+1 − 1
p−1

τ (pa ) = a + 1
Chứng minh. Các ước của pa là 1, p, p2 , pa . Do đó, pa có đúng a+1 ước dương,
a+1
τ (pa ) = a + 1. Mặt khác, σ(pa ) = 1 + p + p2 + ... + pa = p p−1−1 .
Định lý 2.2.6. Giả sử f là một hàm có tính chất nhân. Khi đó hàm
F (n) = d|n f (d) cũng có tính chất nhân.
Chứng minh. Ta sẽ chỉ ra rằng nếu m, n là các số nguyên dương nguyên tố
cùng nhau thì F (mn) = F (m).F (n). Gỉa sử (m, n) = 1, ta có:

F (mn) =

f (d).
d|mn

Vì (m, n) = 1 nên theo bổ đề 1.1, mỗi ước số của mn có thể viết duy nhất
dưới dạng các ước d1 của m và d2 của n và d1 , d2 nguyên tố cùng nhau, đồng
15


thời mỗi cặp ước số d1 của m và d2 của n tương ứng với ước d1 .d2 của mn.

Do đó ta có thể viết: F (mn) = d1 |m f (d1 d2 ).
d2 |n

Vì f là hàm có tính chất nhân và (d1 , d2 ) = 1 nên

F (mn) =
d1 |m

f (d2 ) = F (m).F (n)

f (d1 ).

f (d1 )f (d2 ) =

d2 |n

d1 |m

d2 |n

Tính chất 2.2.7. (i) Hàm σ(n) là hàm nhân tính, tức là : Với mọi số tự
nhiên n1 , n2 nguyên tố cùng nhau thì σ(n1 .n2 ) = σ(n1 ).σ(n2 ).
Chứng minh. Ta có σ(1) = 1 nên σ khác 0. Ta còn phải chứng minh
∀a, b ∈ N ∗ , UCLN(a, b) = 1 thì σ(ab) = σ(a)σ(b).
Thật vậy, giả sử x1 , x2 , ..., xτ (a) là các ước tự nhiên của a và y1 , y2 , ..., yτ (b)
là các ước tự nhiên của b. Ta có d|ab ⇔ d = xi yj (i = 1, 2, ..., τ (a); j =
1, 2, ..., τ (b)) nên ta được
τ (a)

σ(ab) =


d=
d|ab

x i yj =

xi
i=1

i=1,2,...,τ (a)

τ (b)

yj = σ(a)σ(b).
j=1

j=1,2,...,τ (b)

(ii) Nếu p là số nguyên tố thì σ(p) = 1 + p
Chứng minh. Được suy ra từ mệnh đề 1.2
(iii) Giả sử n là số nguyên dương và có khai triển chính tắc n = pα1 1 pα2 2 ...pαk k
α +1

thì σ(n) =

α +1

α +1

p1 1 −1 p2 2 −1 pk k −1

p1 −1 . p2 −1 ... pk −1 .

Chứng minh. Do hàm σ có tính chất nhân nên ta có

σ(n) = σ(pa11 )σ(pa22 )...σ(pas s ).

16


2.3

Hàm tổng các chữ số của số tự nhiên n

Định nghĩa 2.3.1. Giả sử n là một số tự nhiên. Ta định nghĩa S(n) là hàm
tổng các chữ số của n, khi biểu diễn trong hệ thập phân.
Với n là số nguyên dương. Ta có:
Tính chất 2.3.2. S(n) ≡ n (mod 9).
Chứng minh. Giả sử trong biểu diễn thập phân, số nguyên dương n có dạng:
n = αk αk−1 ...α2 α1 α0 |10
Khi ấy

n = α0 + 10α1 + 102 α2 + ... + 10k−1 αk−1 + 10k αk
S(n) = α0 + α1 + α2 + ... + αk−1 + αk
Vì thế

n − S(n) = 9α1 + 99α2 + ... + 99...9 αk−1 + ... + 9.9...9 αk . (1.1)
(k−1)

số 9


k số 9

.
Từ (1.1) suy ra [n − S(n)].. 9 hay S(n) ≡ n (mod9), suy ra điều phải chứng
minh.
Tính chất 2.3.3. 0 < S(n) ≤ n
Tính chất 2.3.4. S(n) = n ⇔ 1 ≤ n ≤ 9
Chứng minh. Ta có n = αk αk−1 ...α2 α1 α0 |10 . Vì n > 0 nên αk > 0. Ngoài ra
αi ∈ {0, 1, 2, ..., 9} với mọi i = 1, 2, ..., k.
Từ đó, do S(n) = αk + αk−1 + ... + α1 + α0 suy ra S(n) > 0.
Lại thấy từ (1.1) thì S(n) ≤ n và S(n) = n ⇔ α1 = α2 = ... = αk = 0 ⇔
α0 > 0 ⇔ α0 ∈ {1, 2, ..., 9}. Đó là điều phải chứng minh.
Tính chất 2.3.5. S(m + n) ≤ S(m) + S(n), với mọi m, n nguyên dương
Chứng minh. Giả trong hệ thập phân, n và m lần lượt có dạng:

n = αk αk−1 ...α1 α0 |10

17


m = βs βs−1 ...β1 β0 |10
Không giảm tổng quát, ta có thể cho là n ≥ m ⇒ k ≥ s. Ta có thể viết lại
m dưới dạng sau đây m = 00...0 βs βs−1 ...β1 β0 |10
(k−s)

Đặt

βi =

số 0





βi với i = 0, 1, 2, ..., s


0 với i = s + 1, ..., k.

Vì thế luôn luôn có thể coi n và m có cùng loại biểu diễn sau:

n = αk αk−1 ...α2 α1 α0 |10
m = βk βk−1 ...β2 β1 β0 |10
trong đó 0 ≤ αi , βi ≤ 9, với mọi i = 0, 1, 2, ..., k và αi , βi nguyên.
Ta sẽ chứng minh bất đẳng thức S(m + n) ≤ S(m) + S(n) với mọi m, n
nguyên dương bằng phép quy nạp theo k.
-Nếu k = 0, khi đó n = α0 , m = β0 suy ra S(n) + S(m) = α0 + β0
Ta có m + n = α0 + β0 , do vậy



α0 + β0 nếu α0 + β0 ≤ 9
S(m + n) =


(α0 + β0 − 10) + 1 nếu α0 + β0 > 9
Chú ý rằng do 0 < α0 ≤ 9; 0 < β0 ≤ 9 nên α0 + β0 ≤ 18, suy ra
α0 + β0 − 9 ≤ 9 < α0 + β0 ( khi α0 + β0 > 9)
Tóm lại ta luôn chứng minh được S(m + n) ≤ S(m) + S(n), trong trường
hợp k = 0. Vậy điều khẳng định đúng khi k = 0.

- Giả sử điều khẳng định đã đúng đến k − 1, tức là với mọi biểu diễn trong hệ
thập phân: n = αk−1 ...α2 α1 α0 |10 , m = βk−1 ...β2 β1 β0 |10 ( trong đó ít nhất một
trong hai số αk−1 , βk−1 phải lớn hơn 0), ta luôn có: S(m + n) ≤ S(m) + S(n)
-Xét trường hợp với k, tức là khi n và m biểu diễn như sau:

n = αk αk−1 ...α2 α1 α0 |10 , m = βk βk−1 ...β2 β1 β0 |10
18


ở đây ít nhất một trong hai số αk , βk phải lớn hơn 0.
Ta có thể viết lại : n = 10.αk αk−1 ...α1 α0 ; m = 10.βk βk−1 ...β1 β0
Vì 10.αk αk−1 ...α1 = αk αk−1 ...α1 0 nên suy ra S(n) = S(n ), ở đây n =
βk βk−1 ...β1
Tương tự: 10.βk βk−1 ...β1 = βk βk−1 ...β1 0 nên suy ra S(m) = S(m ), ở đây
m = βk βk−1 ...β1
Rõ ràng ta có : S(n) = α0 + S(n ) và S(m) = β0 + S(m ). Áp dụng giả
thiết quy nạp, ta thấy ngay : S(m + n ) ≤ S(m ) + S(n ). Mặt khác, ta có:
m + n = 10(m + n ) + α0 + β0 nên

S(m + n) ≤ S(m ) + S(n ) + α0 + β0 .
suy ra S(m + n) ≤ S(m ) + S(n ) + α0 + β0 = S(m) + S(n).
Vậy điều khẳng định cũng đúng đến k. Từ đó suy ra điều phải chứng minh.
Mệnh đề 2.3.6. Bằng quy nạp dễ dàng chứng minh được:
Nếu a1 , a2 , ..., ak là các số nguyên dương thì:
k

S(a1 + a2 + ... + ak ) ≤

S(ai )
i=1


S(a1 a2 ...ak ) ≤ S(a1 ).S(a2 )...S(ak ).
Tính chất 2.3.7. S(mn) ≤ S(m).S(n), với mọi m, n nguyên dương.
Chứng minh. Giả sử B có biểu diễn dưới dạng thập phân là:

B = b1 b2 ...bk
Do đó B = bk + 10bk−1 + 102 bk−2 + ... + 10k−1 b1
Trước hết ta có nhận xét sau:
Nếu N là số tự nhiên thì với mọi số p nguyên dương, ta có:

S(10p N ) = S(N )
(Nhận xét này quá hiển nhiên dựa vào trực tiếp từ định nghĩa của hàm S(n)).
Ta có: AB = Abk + 10Abk−1 + 102 Abk−2 + ... + 10k−1 Ab1
Theo chứng minh của tính chất 4, suy ra:

S(AB) = S(Abk + 10Abk−1 + ... + 10k−1 Ab1 )
19


≤ S(Abk ) + S(10Abk−1 ) + ... + S(10k−1 Ab1 ) (1.2)
Lại theo Tính chất 4, ta có

S(Abk ) = S(A + A + ... + A) ≤ S(A) + S(A) + ... + S(A) = bk S(A)
bk

số hạng

A

Tương tự ta có


S(10Abk−1 ) ≤ bk−1 S(10A) = bk−1 S(A);
S(102 Abk−2 ) ≤ bk−1 S(102 A) = bk−2 S(A);
.....
S(10Ak−1 b1 ) ≤ b1 S(10k−1 A) = b1 S(A).
Vì vậy, thay vào (1.2), ta có: S(AB) ≤ (b1 + b2 + ... + bk ).S(A). Do
S(B) = b1 + b2 + ... + bk nên từ đẳng thức trên ta thu được

S(AB) ≤ S(A).S(B)
Đó là điều phải chứng minh.
Chú ý 2.3.8. Theo nguyên lí quy nạp, ta suy ra kết quả sau:
Nếu A1 , A2 , ..., An là các số nguyên dương thì

S(A1 A2 ...An ) ≤ S(A1 ).S(A2 )...S(An ).

2.4

Hàm số các ước τ (n)

Định nghĩa 2.4.1. Số các ước dương của số tự nhiên n được kí hiệu là τ (n).
Ví dụ 2.4.2. τ (1) = 1, τ (2) = 2, τ (n) = 6.
Tính chất 2.4.3. Hàm τ (n) là hàm có tính chất nhân.
Chứng minh. Ta có τ (1) = 1 nên τ khác 0. Giả sử a, b ∈ N ∗ , UCLN(a, b) = 1,
ta phải chứng minh τ (a.b) = τ (a)τ (b). Trước hết ta chứng minh d|ab ⇔ d =
xy trong đó x|a, y|b và UCLN(x, y) = 1. (1)
20


Thật vậy nếu a = 1 hoặc b = 1 thì (1) là hiển nhiên. Giả sử a > 1, b > 1 và
a = pα1 1 pα2 2 ...pαr r và b = q1β1 q2β2 ...qsβs là dạng phân tích tiêu chuẩn của a và b.

Từ UCLN(a, b) = 1 suy ra p1 , p2 , ..., pr , q1 , q2 , ..., qs là những số nguyên tố đôi
một khác nhau và ab = pα1 1 pα2 2 ...pαr r q1β1 q2β2 ...qsβs là dạng phân tích tiêu chuẩn
của tích ab.
Từ đó

d|ab ⇔ d = pγ11 pγ22 ...pγr r q1δ1 q2δ2 ...qsδs , 0 ≤ γi ≤ αi , 0 ≤ δj ≤ βj (0 ≤ i ≤ r, 0 ≤ j ≤ s)
hay

d|ab ⇔ d = xy
với x = pγ11 pγ22 ...pγr r và y = q1δ1 q2δ2 ...qsγs tức là d|ab ⇔ d = xy với x|a, y|b.
Thêm nữa rõ ràng UCLN(x, y) = 1. Từ kết quả trên ta suy ra được rằng
τ (ab) = τ (a)τ (b.)
Tính chất 2.4.4. Nếu p là số nguyên tố thì τ (p) = 2.
Tính chất 2.4.5. Nếu n = 1 thì τ (n) = 1.Nếu n > 1 và n = pα1 1 pα2 2 ...pαk k là
dạng phân tích tiêu chuẩn của n thì

τ (n) = (α1 + 1)(α2 + 1)...(αk + 1).
Chứng minh. Với n > 1 và k = 1 thì n = pα1 1 có và chỉ có các ước là
1, p1 , p21 , ..., pα1 1 nên ta được τ (pα1 1 ) = α1 + 1.
αk −1 αk
Giả sử mệnh đề đúng với k − 1 ≥ 1. Khi ấy vì UCLN(pα1 1 pα2 2 ...pk−1
, pk ) = 1
α1 α2
αk −1
α1 α2
αk −1
và τ có tính chât nhân nên τ (n) = τ (p1 p2 ...pk−1 ) = τ (p1 p2 ...pk−1 )τ (pαk k ) =
(α1 + 1)(α2 + 1)...(αk−1 + 1)(αk + 1), tức là mệnh đề đúng với mọi số tự nhiên
n > 1.
Ví dụ 2.4.6. n = 360 = 23 32 5 ta có τ (360) = 4.3.2 = 24.


21


Chương 3

Một số ứng dụng của các hàm số học
Trong chương trình phổ thông, các bài toán về số học đóng vai trò quan
trọng trong việc hình thành tư duy toán học. Việc sử dụng các hàm số học
đã giải quyết được những lớp bài toán cơ bản trong các bài toán sơ cấp.
Trong chương này trình bày một số ứng dụng của các hàm số học cơ bản
trong việc giải các bài toán sơ cấp. Ngoài ra, còn có những bài toán tổng
hợp sử dụng một số hàm số khác.

3.1
3.1.1

Ứng dụng của Phi - hàm Ơ-le

Xét đồng dư môđulô của một số nguyên tố

Ví dụ 3.1.1. Giả sử p nguyên tố, r là số tự nhiên nhỏ hơn p sao cho:

(−1)r r! ≡ 1(mod p) (2.1)
Chứng minh rằng:

(p − r − 1)! + 1 ≡ 0(mod p) (2.2)
Chứng minh. Theo định lí Wilson ta có

(p − 1)! + 1 ≡ 0(mod p) (2.3)

Mặt khác, (p − 1)(p − 2)...(p − r) ≡ (−1)r r!(modp). Suy ra

(p − 1)! ≡ (p − r − 1)!(−1)r r!(modp) ≡ (p − r − 1)!(mod p). (2.4)
Từ (2.3) và (2.4) suy ra các đồng dư (2.1) và (2.2) là tương đương nhau.
22