BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG

TRẦN THỊ THU VÂN

HÀM SỐ HỌC VÀ CÁC BÀI TOÁN
LIÊN QUAN ĐẾN DÃY SỐ NGUYÊN
Chuyên ngành : Phương pháp Toán sơ cấp
Mã số:

60.46.40

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

Người hướng dẫn khoa học: TS. TRỊNH ĐÀO CHIẾN

Đà Nẵng - Năm 2013


LỜI CAM ĐOAN

Tôi cam đoan đây là công trình nghiên cứu của riêng tôi.
Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng
được ai công bố trong bất kỳ công trình nào khác.

Tác giả

Trần Thị Thu Vân


DANH MỤC CÁC KÍ HIỆU

Ước chung lớn nhất của m và n

Df(n)

Hàm tổng các ước của f


dn

Lấy tổng theo các ước dương của n


MỤC LỤC
MỞ ĐẦU .......................................................................................................... 1
1. Lý do chọn đề tài ................................................................................... 1
2. Mục đích nghiên cứu ............................................................................. 1
3. Nhiệm vụ nghiên cứu ............................................................................ 1
4. Đối tượng và phạm vi nghiên cứu......................................................... 2
5. Phương pháp nghiên cứu ..................................................................... 2
6. Ý nghĩa khoa học và thực tiễn khoa học ............................................... 2
7. Cấu trúc của luận văn ............................................................................ 2
CHƯƠNG 1 : HÀM SỐ HỌC ........................................................................ 7
1.1. HÀM MOBIUS .......................................................................................... 7
1.2. HÀM EULER........................................................................................... 10
1.3. HÀM τ(n) và HÀM σ(n) ....................................................................... 13
CHƯƠNG 2 : DÃY SỐ NGUYÊN ............................................................... 16
2.1. DÃY SỐ NGUYÊN DẠNG TRUY HỒI TUYẾN TÍNH CẤP 2 ........... 16
2.2. NGUYÊN LÝ DIRICHLET LIÊN QUAN ĐẾN DÃY SỐ NGUYÊN .. 27
2.3. HỆ ĐẾM CƠ SỐ LIÊN QUAN ĐẾN DÃY SỐ NGUYÊN .................... 28
2.4. SỐ PHỨC LIÊN QUAN ĐẾN DÃY SỐ NGUYÊN ............................... 31

tượng học sinh khá giỏi ở phổ thông, đặc biệt đối với hệ phổ thông Chuyên
Toán.
Do đó, nội dung luận văn có ý nghĩa khoa học và mang tính thực tiễn.
2. Mục đích nghiên cứu
Với lý do chọn đề tài nêu trên, luận văn sẽ tập trung nghiên cứu về hàm
số học và các bài toán liên quan đến dãy số nguyên.
3. Nhiệm vụ nghiên cứu
Với lý do chọn đề tài nêu trên, luận văn sẽ tập trung nghiên cứu về hàm
số học và các bài toán liên quan đến dãy số nguyên.


2

4. Đối tượng và phạm vi nghiên cứu
Luận văn chỉ đề cập với một dung lượng nhỏ về hàm số học, vì đây là
khái niệm cơ bản và khó, đã được nhiều giáo trình đề cập. Luận văn dành
nhiều thời gian cho việc nghiên cứu các bài toán liên quan đến dãy số nguyên,
vì đây là phần rất gần gũi với học sinh hệ phổ thông Chuyên Toán.
5. Phương pháp nghiên cứu
Như trên đã nêu, luận văn thuộc chuyên ngành Phương pháp toán sơ
cấp, vấn đề nghiên cứu không phải là mới. Do đó, nội dung của luận văn là
kết quả của một quá trình nỗ lực sưu tầm tài liệu, chọn lọc, phân loại các dạng
toán và tổng hợp lại dưới dạng một tài liệu tham khảo tốt về Toán sơ cấp.
6. Ý nghĩa khoa học và thực tiễn của đề tài
Luận văn có thể là một tài liệu tham khảo khá tốt về phương pháp giải
các dạng toán liên quan đến dãy số nguyên, dành cho các học viên cao học
chuyên ngành Phương pháp toán sơ cấp, các thầy cô giáo, các em học sinh
khá giỏi và những bạn đọc yêu toán quan tâm đến vấn đề này.
7. Cấu trúc luận văn
Với mục đích nghiên cứu đã nêu, ngoài các phần cơ bản như Mục lục,

truy hồi sai phân nêu trên, chẳng hạn bài toán sau đây
“Cho a , b , c là các số thực dương và dãy  an n0 được xác định
như sau
 a1  a, a2  b,

an 2  c

, n  2.
 an 1  a
n 1


Chứng minh rằng tất cả các số hạng của dãy là số nguyên dương khi
và chỉ khi a , b và

a 2  b2  c
là các số nguyên dương”.
ab


4

2.2. Nguyên lý Dirichlet liên quan đến dãy số nguyên
Nguyên lý Dirichlet là một nguyên lý hết sức đơn giản nhưng lại vô
cùng hữu hiệu trong các bài toán chứng minh, đặc biệt là chứng minh sự tồn
tại của một đối tượng thỏa mãn một điều kiện nào đó.
Luận văn đề cập đến việc sử dụng Nguyên lý Dirichlet trong một số bài
toán về dãy số nguyên. Chẳng hạn bài toán sau
Xét n số nguyên dương a1  a2  ...  an  2n sao cho  ai , a j   2n , i  j
(kí hiệu  ai , a j  chỉ bội số chung nhỏ nhất của ai và a j ). Chứng minh rằng

n nghiệm và vì vậy Định lí Viét mới phát huy được tác dụng. Với dãy số

nguyên, số phức có những ứng dụng đặc biệt hữu hiệu trong các bài toán tính
tổng và dãy truy hồi. Đây là một trong những nội dung mà luận văn đề cập.
2.5. Dãy số nguyên dạng n 
Dãy số dạng xn  n  có nhiều tính chất số học khá thú vị (kí hiệu
n  chỉ phần nguyên của số n ). Nếu

1 , thì dãy số   n  n1 là dãy các

số nguyên dương phân biệt có sự biến thiên gần giống một cấp số cộng nhưng
không phải là cấp số cộng. Dãy số này đặc biệt thú vị khi

là số vô tỉ bậc

hai.
Luận văn sẽ đề cập đến một số tính chất của dãy số nêu trên và một
số dạng toán liên quan.
Chương 3. Cực trị trên tập số nguyên
Đây là nội dung trọng tâm thứ hai của luận văn.
Cực trị trên tập số nguyên nói chung và cực trị của một dãy số nguyên
nói riêng là một vấn đề khá rộng. Luận văn chỉ đề cập một số dạng cực trị gần
gũi với chương trình phổ thông hệ Chuyên Toán.
Ta biết rằng, nếu x1, x2 , ... , xn là n số thực dương có tổng bằng S
không đổi thì tích x1 x2 ...xn của chúng đạt giá trị lớn nhất khi và chỉ khi
x1  x2  ...  xn 

S
.
n

1.1 HÀM MOBIUS VÀ CÔNG THỨC NGHỊCH ĐẢO CỦA MOBIUS
Định nghĩa 1.1.1. Hàm số học f là hàm số xác định trên tập các số
nguyên dương và lấy giá trị trong tập số thực.
Ví dụ 1.1.1.
a. Cho hàm f: Z+

R xác định bởi f(n)= sinn. Khi đó f là

hàm số học.
b. Cho hàm số : Z+

Z+ xác định bởi:

(n) = {số các ước dương của n}, n  .
Ví dụ: (12) = 6 vì 12 có 6 ước dương là 1, 2, 3, 4, 6, 12.  là hàm số học.
c. Cho hàm : Z+

Z+ xác định bởi:

 (n) = {tổng các ước dương của n}, n  .
Ví dụ: 18 có các ước dương là 1, 2, 3, 6, 9, 18 nên (18) = 39.  là
hàm số học.
Định nghĩa 1.1.2. Hàm Mobius là hàm số học được xác định bởi (1)
= 1 và với n > 1,
(n) =

(-1)k nếu n = p1p2…pk , với p1, p2,…, pk
là các số nguyên tố phân biệt,
0,


Chứng minh.
- Với n  1 , định lý hiển nhiên đúng.
- Giả sử n  1 . Xét n  p1e p2e ... pke là phân tích chính tắc của n .
1

Khi đó các số hạng trong tổng

  (d )

k

2

khác 0 khi d có dạng là tích các luỹ

dn

thừa đơn của các số p1 , p2 ,..., pk .
Ví dụ :  ( p1 p1 p5 );  ( p2 p4 ) khác 0, còn  ( p32 p6 )  0 .
Vì vậy

  (d )  1    ( p )  ...   ( p )    ( p p )  ...   ( p
1

dn

k

1


I (n) = 1, với mọi n  Z+.
e(n) =

1, nếu n = 1,
0, trường hợp.

Định lý 1.1.2. (Tính chất của tích Dirichlet)
Cho f, g, h là các hàm số học, khi đó
1) f*g=g*f ;
2) (f*g) * h = f * (g*h);
3) f * e = f = e * f ;
4) f * I = Df = I * f ;
5) µ * I = e .
Chứng minh.
1. Đối với tính chất 1), các ước của n có thể xác định theo từng cặp,
n
n
nghĩa là nếu  d ,  là một cặp ước của n thì  , d  cũng là một cặp ước của


d

d



n . Vì vậy các số hạng xuất hiện trong hai tích Dirichlet sau là như nhau:
n
n
( f * g )(n)   f (d ) g   và ( g * f )(n)   g (d ) f  

4. ( f * I )(n)   f (d ) I    f (d ).1  Df (n)
dn

d 

5. Với n = 1 thì (µ*I) (1) = µ(1)I(1)= 1.1 = 1 = e(1);
Với n > 1 thì (µ*I) (n) = (Dµ)(n) = 0 = e(n).
Định lý 1.1.3. (công thức nghịch đảo Mobius)
Nếu f là hàm số học thì f = µ * Df .
Chứng minh: Ta có µ * Df = µ * I * f = e * f = f
1.2. HÀM EULER
Định nghĩa 1.2.1. Hàm Euler φ (còn gọi là φ – hàm Euler) là hàm xác
định trên tập các số nguyên dương được xác định bởi
φ(n) = {số các số nguyên x , 1  x  n và x nguyên tố cùng nhau với n }
Ví dụ 1.2.1.
* φ(1) = 1; φ(2) = 1; φ(3) = 2; φ(4) = 2; φ(5) = 4; φ(6) = 2.
* φ(10) = 4, vì chỉ có các số tự nhiên: 1, 3, 7, 9 < 10 và nguyên tố cùng
nhau với 10.
* Với p là nguyên tố thì  ( p)  p 1 . Điều này là rõ ràng vì tập các số
{1, 2,… , p-1} đều nhỏ hơn p và nguyên tố cùng nhau với p.
Từ định nghĩa của φ – hàm Euler, ta thấy φ là hàm số học. Hơn nữa ta
còn có:


11

Định lý 1.2.1.
D (n)    (d )  n .
dn


dn

Ví dụ 1.2.3. Với n  6 ta có  (6)  2 ;
6

6

6

6

6

  (d ) d   (1). 1   (2). 2   (3). 3   (6). 6
d 6

 1.6  (1).3  (1).2 1.1  2

Định lý 1.2.3. Cho số nguyên dương n có dạng phân tích chính tắc :

n  p1e1 . p2e2 ... pkek . Khi đó :
k



i 1



 ( n)  n   1 

1
1
1

 ...  (1) k
.
pi i  j pi p j
p1 p2 ... pk

 1  p   1  p
 1 
i

1
d

Số hạng đầu là 1, mỗi số hạng sau có dạng  , với d là tích các số
nguyên tố phân biệt. Dấu (1)i trước mỗi số hạng có dấu luân phiên nhau tuỳ
theo số các nguyên tố có trong d. Vì vậy biểu thức trên trở thành


dn

n

đó n 1 
i 1




Chú ý 1.2.1. Nếu p là nguyên tố và k  1 thì


1





 ( p k )  p k 1    p k  p k 1
p

Định nghĩa 1.2.2. Hàm số học f được gọi là nhân tính nếu (m, n) = 1
thì f(mn) = f(m).f(n).
Định lý 1.2.4. Hàm Euler φ là hàm nhân tính.
Chứng minh. Ta có :


 (m)  m. 1 
pm



 1
1
 và  (n)  n. 1   .
p
p
pn 
p nguyên tố


p  


p nguyên tố


13

Vậy

 (m). (n)
m.n

 1
  1   .
r
rmn 
r nguyên tố

1
Do đó :  (m). (n)  (mn).  1    (mn)
rmn



r

r nguyên tố




Do (m, n)  1 nên nếu am và bn thì (a, b)  1 . Vì f là hàm nhân tính
nên
Df (m).Df (n)  
am

 f (ab) .
bn

Nhận xét rằng nếu dm.n thì ta luôn có thể viết d  a.b với am và bn .
Mặt khác nếu am và bn thì abmn . Vì vậy ta cũng viết được d  a.b , trong
đó dm.n . Khi đó ta có: Df (m).Df (n)   f (ab)  Df (mn) .
bn


14

Vậy Df là hàm nhân tính.
Nhận xét 1.3.1.
1. Hàm đồng nhất id(x) = x là hàm nhân tính, vì với m, n, (m, n) = 1 ta
có id (m,n) = mn = id(m).id(n).
Do đó hàm tổng các ước của id cũng là hàm nhân tính.
Ta cũng có Did (n)   id (d )   d   (n) .
dn

dn

Vì vậy hàm tổng các ước σ là hàm nhân tính.
2. Hàm hằng I(n) = 1 là hàm nhân tính, vì với mọi m, n thụôc Z+, (m,n)

1

Khi đó :

2

k

 p1e1 1  1   p2e2 1  1   pkek 1  1 
 (n )  

 .
 ... 
 p1  1   p2  1   pk  1 

và  (n)  (e1 1)(e2 1)...(ek 1) .


15

Chứng minh.
Do  ,  là hàm nhân tính, nên định lý được chứng minh từ bổ để trên.
Ví dụ 1.3.1. Vì 720 = 24.32.5,
nên

 25  1   33  1  52  1 
 .

  2418
 2  1   3  1  5  1 


CHƯƠNG 2

DÃY SỐ NGUYÊN
2.1. DÃY SỐ NGUYÊN DẠNG TRUY HỒI TUYẾN TÍNH CẤP HAI
Xác định dãy số truy hồi sai phân là một trong những bài toán cơ bản
của lý thuyết phương trình sai phân. Các dạng toán về vấn đề này khá phong
phú. Luận văn chỉ đề cập một vấn đề nhỏ của lý thuyết này: dãy số nguyên
dạng truy hồi tuyến tính cấp hai.
Trong mục này đưa ra các tính chất của dãy truy hồi tuyến tính cấp 2
mà dãy các nghiệm của phương trình Pell là một ví dụ cụ thể. Ta có định
nghĩa sau:
Định nghĩa 2.1.1.
Một dãy ( xn , n  0) được gọi là dãy truy hồi (tuyến tính) cấp 2 nếu nó
thoả mãn
xn1  axn  bxn1

n  1,

trong đó a , b là các hằng số không phụ thuộc vào n .
Dễ thấy rằng, nếu biết trước các giá trị của a , b , x0 , x1 thì dãy ( xn ) sẽ
xác định duy nhất. Sau đây ta đưa ra cách xác định dãy ( xn ) thông qua a , b ,
x0 , x1 .

Xét phương trình: x2  ax  b.
Gọi 1 , 2 là hai nghiệm (có thể là số phức) của phương trình. Khi đó
theo Định lý Viet,
a  1  2 , b  12 ,

tức là

xn1   n ((n 1)c1  c2 ),

trong đó c1  x1   x0 , c2   x0 .
Trường hợp 2 : 1  2 . Cộng vế với vế của các đẳng thức trên ta được :
xn1  1n1 x0  2n y0  12n1 y0  ...  1n y0 

tức là : xn1 

1n1  2n1
y ,
1  2 0

1n1  2n1
y   n1 x
1  2 0 1 0

hay xn1  1n1c1  2n1c2 ,
trong đó : c1 

x1  2 x0
x  x
; c2  1 1 0 .
1  2
2  1

Tóm lại, ta đã chứng minh được định lý sau
Định lý 2.1.1.
Cho dãy ( xn , n  0) thoả mãn công thức truy hồi cấp 2
xn1  axn  bxn1 .



Do đó 1 cũng là nghiệm của phương trình f ( x)  0 . Vì 1  1 và
phương trình f ( x)  0 có đúng hai nghiệm 1 , 2 , nên 2  1.
Ta có công thức
ei  cos   i sin  .

Do đó có thể biểu diễn:


1  c  id  c 2  d 2 

c

2
2
 c d

trong đó r  c2  d 2 , cos  

c
c2  d 2

i

, sin  

Khi đó
2  c  id  rei .




c2 

x1  1 x0 x1  rx0 cos   irx0 sin  i ( x1  rx0 cos  ) x0


 .
2  1
2ri sin 
2r sin 
2

Do đó:

 i ( x1  rx0 cos  ) x0 
 i ( x  rx0 cos  ) x0  
xn  r n  cos n  i sin n  
    cos n  i sin n   1
 
2r sin 
2
2r sin 
2 




x  rx0 cos 

 r n  x0 cos n  1

Định lý 2.1.2.
Cho m, a, b là các số nguyên bất kỳ, dãy số nguyên ( xn ) được cho bởi
công thức truy hồi sau:
xn1  axn  bxn1 .

Gọi rn là số dư trong phép chia xn cho m . Khi đó tồn tại một số nguyên
dương N sao cho dãy ( rn , n  N ) tuần hoàn.


20

Chứng minh.
Xét các cặp số (rn , rn1 ) với n  0 . Do rn chỉ nhận nhiều nhất là m giá trị
nên có nhiều nhất m 2 giá trị cụ thể của các cặp (rn , rn1 ) . Theo nguyên lý
Dirichlet, tồn tại hai cặp (rN , rN 1 ) và (rN h , rN h1 ) sao cho rN  rN h , rN 1  rN h1 .
Do đó
xN  xN h , xN 1  xN h1 mod m.

Do dãy ( xn ) thỏa mãn công thức truy hồi xn1  axn  bxn1 nên
xN 2  axN 1  bxN  axN h1  bxN h  xN h2 mod m,

tức là xN 2  xN h2 mod m. Tương tự, bằng quy nạp, ta có ngay
xn  xnh mod m n  N .

Từ đó suy ra rn  rnh với mọi n  N , tức là dãy ( rn , n  N ) tuần hoàn.
Ví dụ 2.1.1. Xét dãy số (an )n1 được xác định bởi các đẳng thức
a1  a2  1, a3  199 và an 1 

1989  an .an 1
, với n  3 .

an2
a2

Nếu n lẻ ta nhận được:
an1  an1 an1  an3
a a

 ...  4 2  11.
an
an2
a3
200an  an 1 nếu n chẵn,

Suy ra: an1  

11an  an 1

nếu n lẻ.

Từ công thức trên, theo lập luận quy nạp, với a1 , a2 , a3 là các số nguyên
dương ta suy ra an1 là số nguyên dương, với mọi n  1 .
Ví dụ 2.1.2. Cho a, b, c là các số thực dương, dãy (an )n1 được xác
định bởi các đẳng thức
an2  c
với n  2 .
a1  a, a2  b và an1 
an1

Chứng minh rằng tất cả các số hạng của dãy là số nguyên dương khi
a 2  b2  c