1
ĐỀ CƯƠNG BÀI GIẢNG HỌC PHẦN

SỐ HỌC

(TÀI LIỆU DÙNG CHO SINH VIÊN ĐHSP TOÁN)

2

CHƯƠNG 1
Lý thuyết chia hết trong vành số nguyên
Số tiết: 7 (Lý thuyết: 5 tiết; bài tập, thảo luận: 2 tiết)
*) Mục tiêu:
- Sinh viên hiểu được các khái niệm về lý thuyết chia hết trong vành số nguyên: Quan hệ chia
hết và phép chia với dư; ước, ước chung lớn nhất, bội, bội chung nhỏ nhất; số nguyên tố; phần
nguyên và phần phân của một số thực
- Sinh viên hiểu được các tính chất của phép chia hết, phép chia với dư, ước chung lớn nhất,
bội chung nhỏ nhất, số nguyên tố, định lý cơ bản của số học và phân tích tiêu chuẩn của

i là
chia hết cho
m
ộ
t s
ố
nguyên
b
, hay
b chia hết cho a

n
ế
u t
ồ
n t
ạ
i m
ộ
t s
ố
nguyên
c
sao cho
a + bc
. Khi
a
chia h
ế
t cho

ủ
a
b
.
Nhận xét 1.1.2.

a
chia h
ế
t cho 0 khi và ch
ỉ
khi
a =
0. Do
đ
ó b
ộ
i c
ủ
a s
ố
0 ch
ỉ
là 0. Tuy nhiên t
ậ
p
các
ướ
c c
ủ

ớ
i m
ọ
i
a
∈
Z
.
(iii)

N
ế
u
a | b
và
b | c
thì
a | c
.
(iv)

N
ế
u
b
≠

0 và
a | b
thì

.
(vi)

N
ế
u
a | b
và
b | a
thì
a b
=
ho
ặ
c
a b
= −
.
(vii)

Quan h
ệ
chia h
ế
t trong
Z
có tính ph
ả
n x
ạ

ớ
i m
ỗ
i c
ặ
p s
ố
nguyên a và b
≠
0, luôn luôn t
ồ
n t
ạ
i duy nh
ấ
t m
ộ
t c
ặ
p s
ố
nguyên
q, r v
ớ
i 0
r
≤
< |b|
để
a = qb + r.

ế
u
d | a
i
v
ớ
i m
ọ
i
i =
1
, ,n
. Ký hi
ệ
u t
ậ
p t
ấ
t c
ả
các
ướ
c chung c
ủ
a
a
1
, ,a
n
là

N
ế
u a
1
, ,a
n
không
đồ
ng th
ờ
i b
ằ
ng 0 thì
Ư
C(a
1
,,a
n
) là m
ộ
t t
ậ
p h
ữ
u h
ạ
n và khác r
ỗ
ng.
(ii)

d

đượ
c g
ọ
i là 1
ướ
c chung l
ớ
n nh
ấ
t
c
ủ
a
các
a
i
n
ế
u
d
là m
ộ
t
ướ
c chung c
ủ
a các
a

1
, ,a
n
là (
a
1
, ,a
n
). N
ế
u (
a
1
, ,a
n
) = 1 thì
a
1
, ,a
n
đượ
c g
ọ
i là
nguyên t
ố
cùng nhau
. Các s
ố
nguyên

=
1 v
ớ
i m
ọ
i
i, j =
1
, ,n
và
i
≠
j.

Nhận xét 1.2.5.
Cho các s
ố
nguyên
a
1
a
n
. Khi
đ
ó ta có:
(i)

N
ế
u

≠
và
–d
c
ũ
ng là
ướ
c chung l
ớ
n nh
ấ
t c
ủ
a
a
1
, ,a
n
. Tr
ườ
ng h
ợ
p này (
a
1
, ,a
n
) là s
ố
l

ế
u
a
1
= a
2
= = a
n
=
0 thì
Ư
C(
a
1
, ,a
n
)
=
Z
,
và do
đ
ó trong tr
ườ
ng h
ợ
p này t
ậ
p
ướ

a
ướ
c chung l
ớ
n nh
ấ
t,
đượ
c suy ra
t
ứ
c kh
ắ
c t
ừ

đị
nh ngh
ĩ
a.
(i)

(0
, a
1
, ,a
n
)
=
(

n
)
=
((
a
1
, ,a
n-1
),
a
n
). Tính ch
ấ
t này ch
ỉ
ra cách tìm
ướ
c chung l
ớ
n nh
ấ
t c
ủ
a nhi
ề
u s
ố

đượ
c quy v

i m
ọ
i
k
∈
Z
.
(v)

N
ế
u
a = bc + d
thì (
a,b
)
=
(
b,d
)
.

(vi)

(0
, a
)
= |a|
v
ớ

ướ
i
đ
ây:
Thuật toán Euclid:
Gi
ả
s
ử

a
và
b
là hai s
ố
nguyên d
ươ
ng v
ớ
i
a

≥

b
và
đặ
t
r
0

+ r
3

…
R
n-2
= r
n-1
q
n-1
+ r
n

R
n-1
= r
n
q
n

v
ớ
i
r
1
> r
2
> > r
n
>

ứ
a quá
b
s
ố

đượ
c. H
ơ
n n
ữ
a t
ừ
(v) ta suy ra
(a, b) = (r
0
, r
1
) = (r
1
, r
2
) = = (r
n-2
, r
n-1
) = (r
n-1
, r
n

, ,a
n
. Khi
đ
ó ta có các kh
ẳ
ng
đị
nh sau:

4

(i)

N
ế
u d =
(
a
1
, ,a
n
)
thì t
ồ
n t
ạ
i các s
ố
nguyên x

1
a
n
c
ủ
a
Z
là nh
ư
nhau.
Định nghĩa 1.2.8.
cho các s
ố
nguyên
a
1
, ,a
n
. S
ố
nguyên
d

đượ
c g
ọ
i là m
ộ
t t
ổ

=
∑
.

T
ừ

đị
nh lý v
ừ
a r
ồ
i ta suy ra các k
ế
t qu
ả
sau:
Hệ quả 1.2.9 (Định lý Bezout).

Các s
ố
nguyên a
1
, ,a
n
nguyên t
ố
cùng nhau n
ế
u và ch

Cho các s
ố
nguyên a
1
a
n
. Khi
đ
ó c là m
ộ
t t
ổ
h
ợ
p tuy
ế
n tính nguyên c
ủ
a a
1
, ,a
n

n
ế
u và ch
ỉ
n
ế
u c là b


nguyên t
ố
v
ớ
i a.
Định lý 1.2.12. (Bổ đề Euclid)

Cho các s
ố
nguyên a, b, c. Khi
đ
ó n
ế
u
(
a,b
)
=
1
và a chia h
ế
t
cho bc thì a chia h
ế
t cho c.
Định nghĩa 1.2.13.
Cho các s
ố
nguyên

nguyên a, b, c. Khi
đ
ó ph
ươ
ng trình ax + by = c có ngi
ệ
m nguyên khi
và ch
ỉ
khi d =
(
a, b
)
chia h
ế
t c.
Cách giải phương trình Diophante ax + by = c.
Gi
ả
s
ử
cho ph
ươ
ng trình Diophante
ax + by = c
v
ớ
i
a, b
không

)
= d
cùng c
ặ
p (
x’, y’
)

∈
Z
2

để

ax’ + by’ = d
. Ki
ể
m tra n
ế
u
c
không chia h
ế
t
cho
d
thì ph
ươ
ng trình vô nghi
ệ

ả
s
ử

a = da’
và
b = db’
. Ta rút ra
đượ
c:
a’(x-x
0
) = b’(y
0
-y).

Do (
a’, b’
)
=
1 và
a’
(
x – x
0
) chia h
ế
t cho
b’
nên theo b

0
0
'
'
x x b t
y y a t
= +


= −

v
ớ
i
t
∈
Z

T
ừ
các b
ướ
c l
ậ
p lu
ậ
n v
ừ
a r
ồ

0
'
'
x x b t
y y a t
= +


= −

(
t
∈
Z
) là nghi
ệ
m t
ổ
ng quát c
ủ
a ph
ươ
ng trình
đ
ã cho.

5

Hệ quả 1.2.15.


d
a
y y t
d

= +




= −


(t
∈
Z
)
Nh
ư
v
ậ
y, m
ấ
u ch
ố
t c
ủ
a l
ờ
i gi

a ph
ươ
ng trình này. Xét ph
ươ
ng trình
ax + by =
c
v
ớ
i (
a, b
)
= d
và
a, b
khác 0,
d
là
ướ
c c
ủ
a
c
. R
ồ
i b
ằ
ng cách bi
ế
n

d
ươ
ng. Bây gi
ờ
ta tìm hi
ể
u thu
ậ
t toán
tìm
d
cùng c
ặ
p (
x’, y’
)

∈
Z
2

để
ax’ + by’ = d.

Tr
ở
l
ạ
i thu
ậ

= r
2
q
2
+ r
3

r
n-2
= r
n-1
q
n-1
+ r
n
r
n-1
= r
n
q
n

d = r
n

và ta c
ầ
n tìm c
ả
c

ba (
x
k
, y
k,
r
k
), sao cho luôn có
ax
k
+ by
k
= r
n
= d
. Do
đ
ó b
ộ
ba (
x
n
, y
k,
r
n
) cho ta l
ờ
i gi
ả

x
1
, y
1,
r
1
)
=
(0
,
1
, b
)
,
cùng d
ạ
ng truy h
ồ
i (
x
k
, y
k,
r
k
)
=
(
x
k-2

ằ
ng
ax
k
+ by
k
= r
k

v
ớ
i m
ọ
i
k =
0
,
1
,…, n
. Do
đ
ó (
x’, y’, d
)
=
(
x
n
, y
n

ủ
a
a
1
, , a
n
n
ế
u
m
chia h
ế
t cho t
ấ
t c
ả
các s
ố

a
i
. S
ố
nguyên
s

đượ
c g
ọ
i là m

chia h
ế
t cho m
ọ
i b
ộ
i chung khác c
ủ
a các
a
i
.
Kí hi
ệ
u
BC(a
1
, , a
n
)
là t
ậ
p t
ấ
t c
ả
các b
ộ
i chung,
BCNN(a

ộ
i chung nh
ỏ
nh
ấ
t c
ủ
a các s
ố

a
1
, ,a
n
.

Nhận xét 1.2.18.
Cho các s
ố
nguyên
a
1
, , a
n
.
(i)

Vì b
ộ
i c

Do
a
1
a
2
a
n
là m
ộ
t b
ộ
i chung c
ủ
a
a
1
, , a
n
, nên
BC(a
1
, , a
n
)
là m
ộ
t t
ậ
p khác r
ỗ

i chung nh
ỏ
nh
ấ
t, và m
ố
i liên h
ệ
gi
ữ
a b
ộ
i chung nh
ỏ
nh
ấ
t
và
ướ
c chung l
ớ
n nh
ấ
t.

6

Định lý 1.2.19.

Cho a và b là hai s

1
, ,a
n
] = [[a
1
, ,a
n-1
], a
n
].
(ii)

N
ế
u a
1
, ,a
n
;à các s
ố
nguyên t
ố
t sánh
đ
ôi thì: [a
1
, ,a
n
] = a
1

n
] = |a
1
,a
2
, …, a
n
|

nói chung là không
đ
úng. Ch
ẳ
ng h
ạ
n (2,2,2) [2, 2, 2] = 2.2 = 4 < 8 = 2.2.2.
Hệ quả 1.2.22
.
Cho a là b
ộ
i chung c
ủ
a n s
ố
nguyên t
ừ
ng
đ
ôi m
ộ

đượ
c g
ọ
i là m
ộ
t
s
ố
nguyên t
ố
n
ế
u
p >
1 và
p
không có m
ộ
t
ướ
c s
ố
nguyên d
ươ
ng nào khác 1 và chính nó. M
ộ
t s
ố
nguyên
m

S
ố
t
ự
nhiên
n

đượ
c g
ọ
i là m
ộ
t
s
ố

chính ph
ươ
ng
, n
ế
u t
ồ
n t
ạ
i m
ộ
t s
ố
nguyên


/


(ii)

N
ế
u m > 1 thì luôn t
ồ
n t
ạ
i m
ộ
t
ướ
c nh
ỏ
nh
ấ
t, l
ớ
n h
ơ
n 1 c
ủ
a m và
ướ
c này là m
ộ


N
ế
u p | ab thì p | a ho
ặ
c p | b.
Định lí 1.3.3 (Euclid).

T
ậ
p h
ợ
p t
ấ
t c
ả
các s
ố
nguyên t
ố
là m
ộ
t t
ậ
p h
ợ
p vô h
ạ
n.
1.3.2. Định lý cơ bản của số học

ố
và phân tích này là suy nh
ấ
t n
ế
u không k
ể

đế
n th
ứ
t
ự
các
th
ừ
a s
ố
.
Hệ quả 1.3.5.

N
ế
u m
ộ
t s
ố
t
ự
nhiên n chia h

ng, khi
đ
ó, n
ế
u x, y là hai s
ố
nguyên th
ỏ
a
mãn
x d y
=
thì x = y = 0.
Định lý 1.3.7
.
1
n
n
p e
+
<

1.4. Phần nguyên và phân tích tiêu chuẩn của n!
1.4.1. Phần nguyên và điểm nguyên.

7

Định nghĩa 1.4.1.
Cho m
ộ

ệ
u
a – [a] = {a}
đượ
c g
ọ
i là
ph
ầ
n phân
hay
ph
ầ
n l
ẻ
c
ủ
a
a
.
Nhận xét 1.4.2.
T
ừ

đị
nh ngh
ĩ
a c
ủ
a phân nguyên và ph

ố
nguyên d
ươ
ng
b
là
[ ]
a
b
.
(ii)

[x] = x khi và ch
ỉ
khi
x
∈
Z
.
(iii) N
ế
u a
∈
Z
và x < a thì [x] < a.
(iv)

N
ế
u x

ủ
a m
ộ
t s
ố
th
ự
c có các tính ch
ấ
t sau
đ
ây:
(i)

N
ế
u
n
∈
Z
thì [a + n] = [a] + n.
(ii)

1 1 1
[ ] [ ] [ ] 1
n n n
i i i
i i i
a a a n
= = =

ng là b
ộ
i c
ủ
a d không l
ớ
n h
ơ
n a
đ
úng b
ằ
ng
[ ]
a
b
.
(iv)

[2a] = [a] + [a +
1
2
].
Định lý 1.4.5. (Sierpinski).

Đặ
t
2
1
10

ẳ
ng
D
trong m
ặ
t ph
ẳ
ng t
ọ
a
độ
(
Oxy
) .
Đ
i
ể
m
(x
1
, y
1
)
thu
ộ
c D
v
ớ
i
1 1

đị
nh và liên t
ụ
c trên
đ
o
ạ
n [a, b]. G
ọ
i T là s
ố
t
ấ
t c
ả
các
đ
i
ể
m nguyên c
ủ
a mi
ề
n
2
{( , ) |
D x y a x b
= ∈ ≤ ≤
Z
;

!
s
s
n p p p
α
α α
=
v
ớ
i
2 3
[ ] [ ] [ ] ; 1, , .
i
i i i
n n n
i s
p p p
α
= + + + =

*) Tài liệu tham khảo:

[1] D
ươ
ng Qu
ố
c Vi
ệ
t (2009), Lý thuy
ế

Đứ
c Th
ị
nh (1977), Giáo trình S
ố
h
ọ
c, Nhà xu
ấ
t b
ả
n Giáo d
ụ
c, Hà N
ộ
i.
*) Câu hỏi, bài tập, nội dung ôn tập và thảo luận
1.1. Quan hệ chia hết và phép chia với dư
1.1.1.
Ch
ứ
ng minh r
ằ
ng:
(i)

Trong 3 s
ố
nguyên liên ti
ế

i có 1 s
ố
chia h
ế
t cho n.
1.1.2.
Ch
ứ
ng minh r
ằ
ng:
(i)

Tích c
ủ
a 3 s
ố
nguyên liên ti
ế
p chia h
ế
t cho 6.
(ii)

Tích c
ủ
a 2 s
ố
ch
ẵ

ố
nguyên b
ấ
t k
ỳ
ph
ả
i có hai s
ố
có hi
ệ
u chia h
ế
t cho 10.
1.1.4.
Ch
ứ
ng minh r
ằ
ng:
(i)

n
3
– n chia h
ế
t cho 6 v
ớ
i m
ọ

ề
u ki
ệ
n a
2
+ 2b
2
=
4c
2

1.1.6.
p, q là các s
ố
nguyên t
ố
l
ớ
n h
ơ
n 3. Ch
ứ
ng minh r
ằ
ng: (p
2
– q
2
) chia h
ế


1
2007
+ 2
2007
+ …. + n
2007
cho s
ố
n + 2.
1.1.9.
Cho m, n là hai s
ố
nguyên d
ươ
ng.
Tìm d
ư
c
ủ
a phép chia (5m)!(5n)! Cho m!n!(3m+n)!(3n+m)!.
1.1.10.
Cho m, n là nh
ữ
ng s
ố
nguyên d
ươ
ng. Tìm d
ư

ươ
ng n, t
ổ
ng
1 2
n n
x x
+
là m
ộ
t s
ố
nguyên và tìm d
ư
c
ủ
a phép chia s
ố

đ
ó cho 3.
1.2. Ước chung lớn nhất và bội chung nhỏ nhất.

1.2.1.
Ch
ứ
ng minh chi ti
ế
t t
ấ

1.2.3.
Cho các s
ố
nguyên
a, b, k, l, m, n
. Ch
ứ
ng minh r
ằ
ng:
(i)

(
5
a +
3
b,
13
a +
8
b) = (a, b).
(ii)

Ch
ứ
ng minh r
ằ
ng n
ế
u

ằ
ng: N
ế
u
a, n
≥

2 và
a
n
–
1

là m
ộ
t sô nguyên t
ố
thì
a =
2 và
n
là m
ộ
t s
ố

nguyên t
ố
.
1.2.6.

ng
m, n
v
ớ
i
m > n
. Ch
ứ
ng minh r
ằ
ng
2 2
(2 1,2 1) 1
m n
+ + =
.
1.2.8.
Cho
m, n
là hai s
ố
t
ự
nhiên th
ỏ
a mãn
(
2
m
–

2
,
sao cho
a
1
= a
2
=
1
; a
n+2
= a
n
a
n+1
, n=
1
,
2
,

Ch
ứ
ng minh r
ằ
ng
a
1946

không chia h


1. V
ớ
i s
ố
nguyên
m
ta
đặ
t
t
0
= m, t
i
= f(f(…(f(m))…))
,
i
l
ầ
n
f
. Ch
ứ
ng minh r
ằ
ng
(t
t
, t
s

n
f
. Ch
ứ
ng minh r
ằ
ng các s
ố
trang
dãy
m, a
1
(m), a
2
(m)
đ
ôi m
ộ
t nguyên t
ố
cùng nhau v
ớ
i m
ọ
i s
ố
t
ự
nhiên
m >

,
n n
x x n N
+ ∈

Ch
ứ
ng minh r
ằ
ng
a
n
là m
ộ
t s
ố
nguyên và
a
n
không chia h
ế
t cho 3, 4, 5.
1.2.12.
Cho
f(x)
là m
ộ
t
đ
a th

ọ
i
n
≥

1. Ch
ứ
ng minh r
ằ
ng
(a
m
, a
n
) = a
(m, n)
.
Khi
f(x) =
9
1
2
i
i
x
=
+
∑
9
1

= F
n+1
= F
n

v
ớ
i
n
≥

1. Ch
ứ
ng minh r
ằ
ng
(F
r
,
F
s
) = F
(r, s)
.

1.2.14.
Cho các s
ố
nguyên
a

ằ
ng
|a
1
a
2
a
n
|
≥

[
a
1
, , a
n
]
( a
1
, , a
n
).

1.2.16.
Cho
ba
s
ố
nguyên d
ươ

ng [1, 2, …., 200] = [101, 102,…., 200].
1.2.18.
Tìm r
ấ
t c
ả
các s
ố
nguyên x và y sao cho 3xy – 7y = 3x + 1.
1.2.19.
Gi
ả
i ph
ươ
ng trình nghi
ệ
m nguyên 13x + 21y = 12
1.2.20.
Gi
ả
i ph
ươ
ng trình nghi
ệ
m nguyên 3x + 31y = 15.

10

1.3 Số nguyên tố và Định lí cơ bản của số học
.

ng t
ồ
n t
ạ
i nhi
ề
u vô h
ạ
n các s
ố
nguyên t
ố
d
ạ
ng 4n
+
3 v
ớ
i
n
∈
ℕ
.
1.3.3.
Tìm s
ố
nguyên p sao cho p + 10 và p + 14 c
ũ
ng là nh
ữ

nguyên t
ố
thì s
ố
còn l
ạ
i là h
ợ
p s
ố
.
1.3.5.
Tìm t
ấ
t c
ả
các s
ố
t
ự
nhiên n
để
sao cho n(n+1)(n+2)(n+3) có
đ
úng 3
ướ
c nguyên t
ố
.
1.3.6.

ỉ
khi
i
α
chia h
ế
t cho
r
v
ớ
i m
ọ
i
i =
1
,
2
,
3
,s.
1.3.7
. Gi
ả
s
ử

p, q
là hai s
ố
nguyên t

ng v
ợ
i m
ọ
i s
ố
nguyên d
ươ
ng
n
thì t
ừ

ab = c
n
ta suy ra t
ồ
n t
ạ
i
x, y
+
∈
ℕ

để
sao cho
a = x
n
và

1.3.10.
S
ố
4
p +
1 có là m
ộ
t s
ố
nguyên t
ố
không? N
ế
u bi
ế
t các s
ố

p
, 2
p+
1 là nguyên t
ố
và
p >
3
.

1.3.11.
Gi

ng
n =
2
k
v
ớ
i s
ố
nguyên d
ươ
ng
k
nào
đ
ó.
1.3.12.
Bi
ế
t
p
và 8
p
2
+
1 là các s
ố
nguyên t
ố
, tìm
p

ố

p
cho 30 ch
ỉ
có th
ể
là 1 ho
ặ
c
m
ộ
t s
ố
nguyên t
ố
.
1.3.14.
Cho
đ
a th
ứ
c
f(x) = x
2
+ x +
41. Xét các s
ố

f(


f(
0
), f(
1
),…, f(
15
).
Nh
ữ
ng s
ố
nào là nguyên
t
ố
.
1.3.16.
Ch
ứ
ng minh r
ằ
ng không t
ồ
n t
ạ
i m
ộ
t
đ
a th


1.4.1
Ch
ứ
ng minh r
ằ
ng
a
ab
b
c c
 
 
 
 
 
 
 
=
 
 
 
 
 
v
ớ
i m
ọ
i
a, b

–x
]
= –
[
x
]
.
1.4.4
. Cho n là m
ộ
t s
ố
nguyên d
ươ
ng hãy xác
đị
nh ph
ầ
n nguyên
[ ( 1)( 2)( 3)]
n n n n+ + +11

1.4.5.
Ch
ứ
ng minh r
ằ

n c
ủ
a
[(1 3) ]
n
+
v
ớ
i
n
là m
ộ
t s
ố
nguyên d
ươ
ng
cho tr
ướ
c.
1.4.7
. Cho
,
a b
∈
R
và
a, b
≥


i s
ố
nguyên d
ươ
ng
n
b
ấ
t kì và s
ố
th
ự
c
a
≥

0

ta có b
ấ
t
đẳ
ng th
ứ
c
[ ]
[
]
[ ] [2 ]


[
ln
3]
+ +
[
ln n
]
+
[
e
]
+
[
e
2
]
+ +
[
e
k
]
= nk.
1.4.10.
Tìm s
ố
m
ũ
c
ủ
a s

ự
nhiên
n
≥

1
.
1.4.12
. Ch
ứ
ng minh r
ằ
ng
(2 )!(2 )!
! !( )!
m n
m n n m
+
là m
ộ
t s
ố
nguyên v
ớ
i m
ọ
i s
ố
t
ự

[ ] [x + ] [ ]
n
i
x nx
i
−
=
+ =
∑
.
1.4.14.
Ch
ứ
ng minh r
ằ
ng
1 1

n n n k
n
k k k
+ + −
     
+ + + =
     
     
.
1.4.15
. Ch
ứ

∑ ∑
. 12

CHƯƠNG 2
Các hàm số học
S
ố
ti
ế
t: 4 (Lý thuy
ế
t: 3 ti
ế
t; bài t
ậ
p, th
ả
o lu

σ
, hàm Euler
( )
n
ϕ
; s
ố
hoàn thi
ệ
n; Hàm Mobius.
- Sinh viên hi
ể
u
đượ
c các tính ch
ấ
t c
ủ
a các hàm s
ố
h
ọ
c; các hàm s
ố
h
ọ
c quan tr
ọ
ng: hàm
( )

Định nghĩa 2.1.1.
M
ộ
t hàm s
ố
f
xác
đị
nh trên t
ậ
p
+
ℕ
(t
ậ
p các s
ố
nguyên d
ươ
ng) và nh
ậ
n các giá
tr
ị
trong các tr
ườ
ng các s
ố
ph
ứ


f
:
+
→
ℕ ℂ
.
Định nghĩa 2.1.2.
Hàm s
ố
h
ọ
c
f
khác hàm không,
đượ
c g
ọ
i là m
ộ
t
hàm nhân
,
n
ế
u
(
)
(
)

ủ
a ph
ầ
n này, ta gi
ớ
i h
ạ
n ch
ỉ
nói
đế
n các
ướ
c
d
ươ
ng và
|
d n
∑
l
ấ
y theo t
ấ
t c
ả
các
ướ
c d
ươ

ọ
i hàm nhân f ta có
| 0 1
1 1
( ) ( ( )) (1 ( ))
i i
s s
i i
j j
d n j j
i i
f d f p f p
α α
= =
= =
= = +
∑ ∑ ∑
∏ ∏
.

2.1.3. Hàm
( )
n
τ
và hàm
( )
n
σ
cùng các số hoàn thiện
V

ổ
ng
các
ướ
c nguyên d
ươ
ng c
ủ
a
n
. Khi
đ
ó d
ễ
th
ấ
y
,
τ σ
là nh
ữ
ng hàm s
ố
h
ọ
c.
Bổ đề 2.1.5.

N
ế

∏

(ii)

|
1
1 (1 )
s
i
d n
i
α
=
= +
∑
∏

(iii)

| 1
1
(1 )
i
s
j
i
d n j
i
d p
α

hoàn thi
ệ
n
n
ế
u
( ) 2
n n
σ
=
.
Định lí 2.1.8. (Euclid- Euler)

M
ộ
t s
ố
ch
ẵ
n m là m
ộ
t s
ố
hoàn thi
ệ
n khi và ch
ỉ
khi m có d
ạ
ng

n
…
nguyên t
ố
v
ớ
i
n
đượ
c lí kí hi
ệ
u là
( )
n
ϕ
. D
ễ
dàng th
ấ
y r
ằ
ng
( )
n
ϕ
là
m
ộ
t hàm s
ố

ϕ ϕ
−
= − = −
v
ớ
i
α
nguyên d
ươ
ng.
Bổ đề 2.1.10.
Hàm Euler là m
ộ
t hàm nhân.
Định lí 2.1.11.

N
ế
u m
ỗ
i s
ố
nguyên d
ươ
ng n > 1 có phân tích tiêu chu
ẩ
n
1 2
1 2
s

ng n > 1 ta có
|
( )
d n
d n
ϕ
=
∑
.
2.1.5. Một vài ví dụ về các hàm số học
Ví dụ 2.1.14.
V
ớ
i m
ọ
i s
ố
nguyên d
ươ
ng m, n ta luôn có:
(i)

( ) ( ) ( ).
m n mn
τ τ τ
+ ≥

(ii)

( ) ( ) ( ).

ng
| | '|( / )
( ) ( ) ( ') ( )
d n d n d n d
n
d g f d d
d
µ µ
=
∑ ∑ ∑
v
ớ
i m
ọ
i s
ố
nguyên d
ươ
ng n.
Ví dụ 2.1.16.
Ch
ứ
ng minh r
ằ
ng
( ) (1 ln )
n n n
σ
< +
và

µ

đượ
c xác
đị
nh b
ở
i
1 2
2
1 neu 1
( ) ( 1) neu co phan tich tieu chuan
0 neu chia het cho voi nguyen to
k
k
n
n n n p p p
n p p
µ
=


= − =




được gọi là hàm Mobius.
Bổ đề 2.2.2. Hàm Mobius là một hàm nhân.
Định lí 2.2.3. Nếu một số nguyên dương n có phân tích chính tắc

( ) 0
d n
d
µ
=
∑
.
2.2.2. Luật thuận nghịch
Đị
nh lí sau đây được gọi là Luật thuận nghịch Dedekind-Liouville.
Định lí 2.2.5. Cho f là một hàm nhân, và một hàm số học g được xác định bởi
|
( ) ( )
d n
g n f d
=
∑
.
Khi đó ta có
|
( ) ( ) ( )
d n
n
f n d g
d
µ
=
∑
.
Hệ quả 2.2.6. Cho một số nguyên n > 1 có phân tích tiêu chuẩn


(ii)

|
( ) ( )
d n
d n
d n
µ ϕ
=
∑

(iii)

|
( ) ( ) 1
d n
n
d
d
µ τ
=
∑

(iv)
|
( ) ( )
d n
n
d n

|
1
1
1 1
( )
1
i
s
i
d n
i
i
p
n
d n p
α
δ
+
=
−
= =
−
∑
∏

Định lí 2.2.8. Cho f là một hàm nhân. Khi đó với mọi số nguyên dương m và n ta luôn có
[
]
( , ) (( , )) ( ) ( )
f m n f m n f m f n

k n
n n
k
ϕ
≤ ≤
=
=
∑
.
2.1.3. Chứng minh rằng với mọi số tự nhiên lẻ n ta có
!
| 2 1
n
n
−
.
2.1.4. Chứng minh rằng nếu n lẻ thì
( ) ( ) (mod 2)
n n
σ τ
≡
.
2.1.5. Chứng minh rằng nếu
7 (mod 8)
n
≡
thì
( ) 0 (mod 8)
n
σ

α β
=
và
( ) 120
n
ϕ
=

2.1.7 Tìm giá trị của n biết:
(i)
( ) 12
n
ϕ
=

(ii)

( ) 17
n
ϕ
=15

(iii)
( ) 24
n
ϕ
=

n
τ
là một số lẻ khi và chỉ khi n là một số chính phương.
2.1.11 Chứng minh rằng: nếu p là một số nguyên tố và
2
n
≥
thì
2
1
( )
n
p
σ
−
là hợp số
2.1.12 Số tự nhiên n được gọi là một số thừa nếu
( ) 2
n n
σ
>
và được gọi là một số thiếu nếu
( ) 2
n n
σ
<
. Chứng minh rằng:
(i) Lũy thừa một số nguyên tố là một số thiếu.
(ii)
Có vô số số tự nhiên n thỏa mãn

τ
.
2.1.15 Cho hai số tự nhiên
, 1
m n
≥
. Chứng minh rằng:
[
]
( ) ( , ) ( , )
mn m n m n
ϕ ϕ
=

2.1.16 Chứng minh rằng nếu
( )
n s
ϕ
=
thì
2
log
2.3
s
n ≤
.
2.1.17 Giả sử
1
2 (mod 4)
k

(i)

( ) ( )
ab d n
ϕ ϕ
=
.
(ii)

( ) ( ) ( ) ( )
ab d d a b
ϕ ϕ ϕ ϕ
=
.
(iii)

( ) ( ) ( ) ( )
a b d n
ϕ ϕ ϕ ϕ
=
.
2.1.19 Cho một số nguyên tố
p
. Chứng minh rằng:
(i)
Nếu
1 (mod 4)
p
≡
thì

( ) 2( )
n n m
σ
= +
.
2.1.21 Chứng minh rằng: nếu
n
là một số hoàn thiện thì
|
2
1
p n
p
p
>
−
∏
.
2.1.22 Chứng minh rằng nếu số lẻ
n
là một số hoàn thiện thì
2
1
k
r m
i
i
n p q
=
=

s p
=
=
∑
. Chứng
minh r
ằng khi đó giữa
n
s
và
1
n
s
+
có ít nhất một số chính phương với mọi
n
nguyên dương.
2.2.2. Chứng minh rằng
n
n
p
p
   
−
 
 
   
chia hết cho
p
với

=
 
 
 
 
∑
.
2.2.5.
Tìm công th
ứ
c tính
|
( ) ( / )
d n
d n d
µ µ
∑
.
2.2.6.
Kí hi
ệ
u
1 1 1 1
!(1 ( 1)
1! 2! 3! !
n
n
D n
n
= − + − + + − . Ch

i m
ọ
i s
ố
t
ự
nhiên n. H
ỏ
i
( )
v n
có ph
ả
i là hàm nhân hay không?
2.2.8.
T
ậ
p các hàm s
ố
h
ọ
c v
ớ
i phép toán x:
0
( x )( ) ( ) ( )
n
i
f g n f i g n i
=

ng n.
2.2.10.
Ch
ứ
ng minh r
ằ
ng
2
|
1 1 ( )
( ) ( )
d n
d
n n d
µ
ϕ ϕ
=
∑
v
ớ
i m
ọ
i s
ố
nguyên
2
n
≥
.


t; bài t
ậ
p, th
ả
o lu
ậ
n: 3 ti
ế
t)
*) Mục tiêu:

- Sinh viên hi
ể
u
đượ
c các khái ni
ệ
m: quan h
ệ

đồ
ng d
ư
, th
ặ
ng d
ư
, vành các l
ớ
p th

ớ
p th
ặ
ng d
ư
, c
ă
n
nguyên th
ủ
y và ch
ỉ
s
ố
.
- Sinh viên v
ậ
n d
ụ
ng gi
ả
i các bài t
ậ
p liên quan.
3.1. Quan hệ đồng dư và thặng dư
3.1.1 Quan hệ đồng dư
Định nghĩa 3.1.1.
Cho m
ộ
t s

i b modulo m,
thì
ta vi
ế
t
a b
≡
(mod
m)
và gọ
i
đó là
m
ộ
t
đồ
ng d
ư
th
ứ
c.
Nhận xét 3.1.2.

a b
≡
(mob m) khi
và chỉ
khi a
và
b chia cho m (v

(i)
a b
≡
( mod m) khi
và chỉ
khi
a b mt
≡ +
v
ớ
i
t
∈
ℤ
.
(ii) Quan h
ệ đồ
ng d
ư
modulo m
là
m
ộ
t quan h
ệ
t
ươ
ng
đươ
ng trong t

modulo m.
Mệnh đề 3.1.5.
S
ố cá
c l
ớ
p th
ặ
ng d
ư
modulo m
đú
ng b
ằ
ng m.
3.1.2. Hệ thặng dư
Định nghĩa 3.1.7.
N
ế
u t
ừ
m
ỗ
i l
ớ
p th
ặ
ng d
ư
modulo m ta l

ệ
th
ặ
ng d
ư

đầ
y
đủ
modulo m. N
ế
u t
ừ
m
ỗ
i l
ớ
p th
ặ
ng d
ư
modulo m ta
l
ấ
y ra m
ộ
t
đạ
i di
ệ


đầ
y
đủ
không âm
bé
nh
ấ
t modulo m.
Nhận xét 3.1.8.
T
ừ đị
nh
nghĩ
a
củ
a m
ộ
t h
ệ
th
ặ
ng d
ư

đầ
y
đủ
ta suy ra: M
ộ

ệ
th
ặ
ng d
ư

đầ
y
đủ
không âm
bé
nh
ấ
t modulo m
là
{
}
0,1, , 1
m
−
.
Cò
n h
ệ
th
ặ
ng d
ư

đầ

− − +
 
 
khi m
lẻ và

+
, 1, , 1
2 2 2
m m m
 
− − + −
 
 
ho
ặ
c
1, 2, ,
2 2 2
m m m
 
− + − +
 
 
khi m ch
ẵ
n

18


y
giá trị
trong
toà
n b
ộ
m
ộ
t h
ệ
th
ặ
ng d
ư

đầ
y
đủ
modulo m,
thì
ax + b
cũ
ng l
ấ
y
giá trị
trong
toà
n b
ộ

1 1
n n
i i
i i
a b
= =
≡
∑ ∑
(mod m)
(ii)

N
ế
u
a b c
≡ +
(mod m)
thì
a c b
− ≡
(mod m)
(iii)

N
ế
u
a b
≡
(mod m)
thì

N
ế
u
a b
≡
(mod m)
thì
ah bh
≡
(mod m)
(vi)

N
ế
u
i i
a b
≡
(mod m) v
ớ
i
1, ,
i n
=
và
x y
≡
(mod
m
),

a b
v
ớ
i (
m,d
) = 1,
thì

a b
d d
≡
(mod
m
)
(viii)

N
ế
u
a b
≡
(mod
m
)
thì
(mod )
ah bh mh
≡

(ix)

a b
≡
(mod
m
)
thì
( , ) ( , )
a m b m
=

(xi)

( ) (mod )
n n
am b b m
+ ≡

Định nghĩa 3.1.12.

( , )
a m

đượ
c cho b
ằ
ng (
b,m
) v
ớ
i m

ố
v
ớ
i mô
đ
un m.

Định nghĩa 3.1.15.
N
ế
u t
ừ
m
ỗ
i l
ớ
p th
ặ
ng d
ư
nguyên t
ố
v
ớ
i modulo
m
, ta l
ấ
y ra m
ộ

gọ
n modulo m.

Nhận xét 3.1.16.
Thông th
ườ
ng, ta
chọ
n h
ệ
th
ặ
ng d
ư
thu
gọ
n modulo
m
t
ừ
m
ộ
t h
ệ
th
ặ
ng d
ư

đầ

v
ớ
i
m

là
( )
m
ϕ
, nên s
ố cá
c ph
ầ
n t
ử củ
a m
ộ
t h
ệ
thu
gọ
n modulo
m
là
( )
m
ϕ
.
Định lí 3.1.18.


ộ
t h
ệ
th
ặ
ng d
ư
thu
gọ
n modulo m,
thì
ax
cũ
ng l
ấ
y
giá trị
trong
toà
n b
ộ
m
ộ
t h
ệ
th
ặ
ng d
ư
thu

t
ậ
p h
ợ
p
củ
a
đú
ng k l
ớ
p th
ặ
ng d
ư
modulo km.
3.2. Vành
m
ℤ

3.2.1 Vành
m
ℤ
các lớp thặng dư modulo m.

19

Cho t
ậ
p th
ươ

ộ
t
và
nh ta
đị
nh
nghĩ
a hai quy t
ắ
c c
ộ
ng
và
nhân
cá
c l
ớ
p th
ặ
ng d
ư
nh
ư
sau
a b a b
+ = +
và
.
a b ab
=

n,
và gọ
i
là phé
p
toá
n c
ộ
ng
và
nhân
cá
c l
ớ
p th
ặ
ng d
ư
modulo
m
.
Cũ
ng d
ễ
ki
ể
m tra
đượ
c r
ằ

ử
không
0
.
Định nghĩa 3.2.1
. Cho m
ộ
t s
ố
nguyên d
ươ
ng
m
. Khi
đó và
nh
m
ℤ
v
ớ
i hai
phé
p
toá
n c
ộ
ng
và
nhân
cá

c
gọ
i
là
m
ộ
t
l
ớ
p
khả nghị
ch, n
ế
u t
ồ
n
tạ
i
m
b ∈
ℤ
để
. 1
a b
=
.
Định lí 3.2.3.

L
ớ

ấ
p
là
( )
m
ϕ

Nhận xét 3.2.5
. Khi
m p
=
là
m
ộ
t s
ố
nguyên t
ố
,
thì mọ
i ph
ầ
n t
ử khá
c không trong
p
ℤ
đề
u
khả

ươ
ng. Khi
đó
v
ớ
i
mọ
i s
ố
nguyên a nguyên t
ố
v
ớ
i m, ta
có
đồ
ng d
ư
th
ứ
c
( )
1(mod )
m
a m
ϕ
≡

Định lí 3.2.7. (Fermat nhỏ)


t s
ố
nguyên t
ố thì
(mod )
p
a a p
≡
v
ớ
i
mọ
i
a
∈
ℤ
.
3.3 Căn nguyên thủy và chỉ số.
3.3.1.Căn nguyên thủy
Định nghĩa 3.3.1.
Cho s
ố
nguyên
m
> 1
và
s
ố
nguyên
a

a
a
modulo
m
, hay
cò
n
gọ
i
là
a

thu
ộ
c s
ố mũ
d
modulo
m
.
Vì
( )
1(mod )
m
a m
ϕ
≡
theo
đ
inh

ố mũ
d
củ
a a modulo m
là ướ
c
củ
a
( )
m
ϕ

(ii)

N
ế
u
(mod )
a b m
≡
thì
a
và
b
cù
ng thu
ộ
c s
ố mũ
modulo m

(iv)

N
ế
u a thu
ộ
c s
ố mũ
d modulo m
và
s
là
m
ộ
t s
ố
nguyên d
ươ
ng sao cho
( , ) 1
s d
=
,
thì
s
a

cũ
ng thu
ộ

nh
1(mod )
d
x m
≡
.
Mệnh đề 3.3.6.
Cho m
ộ
t s
ố
nguyên m >
1
và
m
ộ
t s
ố
nguyên g. Khi
đó
ta
có
:
(i)

g
là
c
ă
n nguyên

, , ,
m
g g g
ϕ
−
l
ậ
p
thà
nh m
ộ
t h
ệ
th
ặ
ng d
ư
thu
gọ
n modulo m.
(iii)
N
ế
u g
là
c
ă
n nguyên
thủ
y modulo m,

1
và
d
2
t
ươ
ng
ứ
ng modulo m v
ớ
i (d
1
,d
2
) =
1
thì
ab thu
ộ
c s
ố
mũ
d
1
d
2
.
Hệ quả 3.3.8.

N

n
a a a
thu
ộ
c s
ố mũ
1 2
, , ,
n
d d d
.
Định lí 3.3.9. Chỉ có cá
c s
ố
2, 4
ho
ặ
c
cá
c s
ố có dạ
ng
, 2
n n
p p
v
ớ
i
p
nguyên t

t
nhó
m cyclic.
Định lí 3.3.12. Giả
s
ử
g
là
c
ă
n nguyên
thủ
y modulo p v
ớ
i p
là
m
ộ
t s
ố
nguyên t
ố lẻ và
0
< g < p.
Khi
đó
t
ồ
n
tạ

ă
n nguyên
thủ
y modulo p
2

Định lí 3.3.13.
N
ế
u p
là
m
ộ
t s
ố
nguyên t
ố lẻ và
g
là
c
ă
n nguyên
thủ
y modulo p
2
thì
g
là
c
ă

nhó
m cyclic khi
và chỉ
khi m
là
2, 4
ho
ặ
c
cá
c s
ố có dạ
ng p
n
,
2
p
n
v
ớ
i c
ặ
p p
là
m
ộ
t s
ố
nguyên t
ố lẻ và

n nguyên
thủ
y d
ươ
ng
bé
nh
ấ
t
xá
c
đị
nh modulo
m
.
Ta bi
ế
t r
ằ
ng khi
đó
{
}
0 1 ( ) 1
*
, , ,
m
m
g g g
ϕ

ộ
t s
ố
nguyên
a
nguyên t
ố
v
ớ
i
m
. Khi
đó
n
ế
u
(mod )( 0).
d
a g m d
≡ ≥

thì
d
đượ
c
gọ
i
là chỉ
s
ố củ

khi
g
đã xá
c
đị
nh. D
ễ
dàng
chỉ
ra n
ế
u
d
=
ind
g
a
thì
s
ố
'
d

không âm
mà
' (mod ( ))
d d m
ϕ
≡
cũ

ế
u
ind
g
a
≡
ind
g
b
(mod ( ))
m
ϕ
.
(ii)ind
g
g
k
≡
k
(mod ( ))
m
ϕ
.
(iii)

ind
g

.

(v)ind
g
(
a
1
a
2
…a
n
)
≡

ind
g
a
1
+
ind
g
a
2
+ … +
ind
g
a

t s
ố
nguyên t
ố
p. Khi
đó
ta
có cá
c k
ế
t
quả
sau
đ
ây:
(i)

V
ớ
i m
ỗ
i s
ố
nguyên a nguyên t
ố
v
ớ
i p., khi
đó
a thu

ế
u (
ind
a, p –
1
)
= 1.

(ii)

Cho
δ
là
m
ộ
t s
ố
t
ự
nhiên cho tr
ướ
c,
và là ướ
c
củ
a (p –
1
). Khi
đó
trong m

−
c
ă
n
nguyên
thủ
y modulo p.
*) Tài liệu tham khảo:

[1] D
ươ
ng Qu
ố
c Vi
ệ
t (2009),
Lý thuy
ế
t s
ố
và
đ
a th
ứ
c,
Nhà xu
ấ
t b
ả
n

ụ
c, Hà N
ộ
i.
*) Câu hỏi, bài tập, nội dung ôn tập và thảo luận
3.1. Quan hệ đồng dư và thặng dư
3.1.1.

Hã
y ch
ứ
ng minh t
ấ
t
cả cá
c k
ế
t
quả cò
n ch
ư
a ch
ứ
ng minh trong ph
ầ
n
lí
thuy
ế
t.

c
đị
nh nh
ư
sau:
1 2 3 4
1, 9, 9, 6
a a a a
= = = =

và
4
n
a
+
b
ằ
ng ch
ữ
s
ố
t
ậ
n
cù
ng
củ
a
3 2 1
2 3 4

Tì
m 2 ch
ữ
s
ố
t
ậ
n
cù
ng
củ
a
cá
c s
ố
9
9
9
7
và
9
9
9
.
3.1.5. Xé
t
dã
y s
ố
nguyên

a
phé
p chia
n
a
cho 1992. ch
ứ
ng minh r
ằ
ng
dã
y
{
}
n
r
tu
ầ
n
hoà
n

22

(ii)

Ch
ứ
ng minh r
ằ

cá
c modulo: 6;10;12;15;16.
3.1.7.
Cho
, ,a b c
∈
ℤ
.
Ch
ứ
ng minh r
ằ
ng
100 10 0
a b c
+ + ≡
(mod 21) khi
và chỉ
khi
2 4 0(mod 21)
a b c
− + ≡
.
3.1.8.
Ch
ứ
ng minh r
ằ
ng n
ế

ứ
ng minh r
ằ
ng d
ư
c
ủ
a
phé
p chia s
ố
2
1
( 1)
p
j
j
=
+
∏
cho p
là
0
ho
ặ
c 4.
3.2. Vành
n
ℤ


ớ
i s
ố
nguyên t
ố
p > 7
hã
y
chỉ
ra
3 2 1(mod 42 )
p p
p
− ≡
.
3.2.3.
Cho n
là
m
ộ
t s
ố
t
ự
nhiên
lẻ
. Ch
ứ
ng minh r
ằ

ỗ
i s
ố
nguyên t
ố
p không t
ồ
n
tạ
i
cá
c s
ố
nguyên a,n v
ớ
i n<1 sao cho
2 3
p p n
a
+ =
.
3.2.6.
Ch
ứ
ng minh r
ằ
ng n
ế
u
( ,561) 1

a n
=
thỏ
a
mã
n
1
1(mod )
n
a n
−
≡
và
1
k
a
−
không chia h
ế
t cho n v
ớ
i
mọ
i s
ố
nguyên
d
ươ
ng k
là ướ

t s
ố
nguyên t
ố
p > 3. Ch
ứ
ng minh r
ằ
ng n
ế
u d
ư

củ
a
phé
p chia s
ố
p cho 8 b
ằ
ng 1
thì
1
2
2 1
p−
−
chia h
ế
t cho

ng:
(i)

1(mod )
n
a m
≡
khi
và chỉ
khi
0(mod )
n d
≡

(ii)

(mod )
n k
a a m
≡ khi
và chỉ
khi
(mod )
n k d
≡

3.2.12.
Cho
( , ) 1
a m

ϕ
.

23

3.2.13.

Kí
hi
ệ
u
2
2 1
n
n
f
= +
v
ớ
i m
ỗ
i s
ố
nguyên d
ươ
ng
n
(
n
f

v
ớ
i
mọ
i s
ố
nguyên d
ươ
ng
m n
≠
.

(iii)

5
0(mod 641)
f
≡

3.2.14
. Cho
p
> 1. Ch
ứ
ng minh r
ằ
ng
cá
c m

i
mọ
i
k
= 1,2,…,
p
– 1
(iii)

1
( 1) (mod )
k k
p
C p
−
≡ −
v
ớ
i
mọ
i
k
= 0,1,…,
p
– 1
3.2.15.
Ch
ứ
ng minh r
ằ

7 7
7 7
−
chia h
ế
t cho 10
cò
n s
ố

5555 2222
2222 5555
+
chia h
ế
t cho 7 .
3.2.17.
Ch
ứ
ng minh r
ằ
ng: N
ế
u
p
là
m
ộ
t s
ố

,
thì
( ) ( )
1(mod )
n m
m n mn
ϕ ϕ
+ ≡
3.3. Căn nguyên thủy và chỉ số
3.3.1.
Cho bi
ế
t
cá
c
nhó
m sau, nh
ó
m
nà
o
là nhó
m cyclic:
* * *
10 14 12
; ;
ℤ ℤ ℤ
.
Hã
y

y modulo 16.
3.3.4.
Liên h
ệ
v
ớ
i
lí
thuy
ế
t
để phá
t bi
ể
u
cá
c k
ế
t
quả và khá
i ni
ệ
m nêu trong
lí
thuy
ế
t, theo ngôn
ng
ữ củ
a

ậ
p
phân vô
hạ
n tu
ầ
n
hoà
n
có
chu
kì
g
ồ
m
a
ch
ữ
s
ố
. Ch
ứ
ng minh r
ằ
ng
a
là
s
ố mũ củ
a 10 modulo

i
ướ
c nguyên t
ố lẻ củ
a
1
p
a
−
thì
ho
ặ
c
là ướ
c
củ
a
1
a
−
ho
ặ
c
là ướ
c
có dạ
ng
2 1
pn
−

2 1
pn
+
.
(iii)
Có
vô s
ố
s
ố
nguyên t
ố có dạ
ng
2 1
pn
+
.
24

CHƯƠNG 4
Phương trình đồng dư
S
ố
ti
ế
t: 9 (Lý thuy
ế

t
ẩ
n, ph
ươ
ng trình
đồ
ng
d
ư
m
ộ
t
ẩ
n b
ậ
c cao, ph
ươ
ng trình
đồ
ng d
ư
b
ậ
c hai.
- Sinh viên hi
ể
u
đượ
c các tính ch
ấ

ươ
ng và
0 1
, , ,
n
a a a
là các s
ố
nguyên. Khi
đ
ó
đồ
ng
d
ư
th
ứ
c ch
ứ
a bi
ế
n
x
có d
ạ
ng
(
)
1
0 1 1

a
≡
/
(mod
m
), thì (1)
đượ
c g
ọ
i là ph
ươ
ng
trình
đồ
ng d
ư
b
ậ
c
n
. Vi
ệ
c tìm t
ấ
t c
ả
các giá tr
ị
nguyên c
ủ

)
1
0 1 1
0 mod
n n
n n
f x a x a x a x a m
−
−
= + + + + ≡
. (*)
S
ố
nguyên
α

đượ
c g
ọ
i là m
ộ
t nghi
ệ
m
đ
úng c
ủ
a ph
ươ
ng trình (*), và vi

ệ
m c
ủ
a ph
ươ
ng trình (*), và vi
ế
t là
(
)
mod
x m
α
≡
, n
ế
u m
ỗ
i ph
ầ
n t
ử
c
ủ
a
(mod )
m
α

đề

đ
úng
α
thì nó c
ũ
ng nh
ậ
n
(
)
mod
x m
α
≡
làm nghi
ệ
m.

Nhận xét 4.1.4.
Ta có m
ộ
t vài nh
ậ
n xét d
ướ
i
đ
ây khi gi
ả
i ph

ỏ
h
ơ
n
m
.
(ii)

T
ậ
p các nghi
ệ
m c
ủ
a (1) nh
ằ
m trong t
ậ
p
{0, 1, , 1}
m
−
. Vì v
ậ
y, ta ch
ỉ
c
ầ
n tìm t
ấ

ó v
ề
nguyên t
ắ
c, (1) bao gi
ờ
c
ũ
ng gi
ả
i
đượ
c, vì ta ch
ỉ
vi
ệ
c duy
ệ
t các nghi
ệ
m
đ
úng c
ủ
a nó
trên m
ộ
t h
ệ
th

n n
n
f x a x a x a
−
= + + + ≡
trên vành
n
Z
.
Định nghĩa 4.1.6.
Hai ph
ươ
ng trình
đồ
ng d
ư

đượ
c g
ọ
i là t
ươ
ng
đươ
ng n
ế
u chúng có cùng m
ộ
t
t

đổ
i t
ươ
ng
đươ
ng sau
đ
ây:
(i)

( ) 0 (mod )
f x m
≡
t
ươ
ng
đươ
ng
( ) 0 (mod )
f x mb m
+ ≡
.
(ii)

( ) 0 (mod )
f x m
≡
t
ươ
ng

u
0 1
( , , , )
n
d UC a a a
∈
và (d, m) = 1 thì
( ) 0 (mod )
f x m
≡
t
ươ
ng
đươ
ng
0
0 (mod )
n
n
a a
x m
d d
+ + ≡

(v)

N
ế
u
0 1

ng d
ư
b
ậ
c nh
ấ
t
ẩ
n
x
là ph
ươ
ng trình có d
ạ
ng sau
đ
ây:
(mod )
ax b m
≡
(2)
trong
đ
ó
, , 0(mod )
a b a m
∈ ≡
/
Z
.

ẽ

có d nghi
ệ
m.
Một vài phương pháp giải phương trình

(mod )
ax b m
≡
.
Theo l
ậ
p lu
ậ
n trên, thì ph
ươ
ng trình b
ậ
c nh
ấ
t luôn
đư
a
đượ
c v
ề
ph
ươ
ng trình d

m c
ủ
a
(mod )
ax b m
≡
,
( , ) 1
a m
=
,
0 ,
a m b m
< < <
. Sau
đ
ây ta nêu m
ộ
t s
ố
cách gi
ả
i
th
ườ
ng
đượ
c s
ử
d

tuy
ệ
t
đố
i nh
ỏ
nh
ấ
t. Vì
( , ) 1
a m
=
, nên khi
x
ch
ạ
y qua m
ộ
t h
ệ
th
ặ
ng d
ư

đầ
y
đủ
modulo
m

ươ
ng trình là
0
(mod )
x x m
≡

Dùng thuật toán đệ quy:
Gi
ả
s
ử

t
∈
ℤ
sao cho
\ ( )
a b mt
+
. Khi
đ
ó
(mod )
b mt
x m
a
+
≡ là
nghi

ng trình trên t
ươ
ng
đươ
ng v
ớ
i
1 1
(mod )
m t b a
≡
. Rõ ràng sau m
ỗ
i b
ướ
c ta
đ
ã chuy
ể
n ph
ươ
ng trình
đ
ã cho v
ề
ph
ươ
ng trình v
ớ
i

≡ nên
( ) 1
. (mod )
m
a a b b m
ϕ
−
≡ .