Đại Học Thái Nguyên
Trường Đại Học Khoa Học
Đỗ Cao Sơn
CÁC HÀM SỐ HỌC VÀ ỨNG DỤNG
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Ĩ TOÁN HỌC
Người hướng dẫn khoa học: GS.TSKH. HÀ HUY KHOÁI
Thái Nguyên - 2011
1Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Công trình được hoàn thành tại
Trường Đại Học Khoa Học - Đại Học Thái Nguyên
Người hướng dẫn khoa học: GS.TSKH. HÀ HUY KHOÁI
Phản biện 1: PGS.TS. Lê Thị Thanh Nhàn
Phản biện 2: TS. Nguyễn Văn Ngọc
Luận văn được bảo vệ trước hội đồng chấm luận văn họp tại:
Trường Đại Học Khoa Học - Đại Học Thái Nguyên
Ngày 09 tháng 09 năm 2011
Có thể tìm hiểu tại
Thư Viện Đại Học Thái Nguyên
2Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1
Mục lục
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1 Các hàm số học cơ bản 5
1.1. Phi - hàm Ơ-le . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . . 5
1.1.2. Các tính chất . . . . . . . . . . . . . . . . . . . . 6
1.2. Hàm tổng các ước số dương của n . . . . . . . . . . . . . 9
1.2.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . . 9

2.4.1. Tìm n thỏa mãn một điều kiện cho trước của τ(n) 40
2.4.2. Một số bất đẳng thức liên quan tới hàm τ(n) . . 43
2.4.3. Tìm số nghiệm của phương trình bằng phương
pháp sử dụng τ(n) . . . . . . . . . . . . . . . . . 45
2.5. Ứng dụng của hàm phần nguyên [x] . . . . . . . . . . . . 46
2.5.1. Bài toán định tính . . . . . . . . . . . . . . . . . 46
2.5.2. Bài toán định lượng . . . . . . . . . . . . . . . . . 50
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . 55
4Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3
Mở đầu
Số học là một trong những lĩnh vực cổ xưa nhất của Toán học, và
cũng là lĩnh vực tồn tại nhiều nhất những bài toán, những giả thuyết
chưa có câu trả lời. Trên con đường tìm kiếm lời giải cho những giả
thuyết đó, có nhiều tư tưởng lớn, nhiều lí thuyết lớn của toán học đã
nẩy sinh. Hơn nữa, trong những năm gần đây, Số học không chỉ là một
lĩnh vực của toán học lí thuyết, mà còn là lĩnh vực có nhiều ứng dụng,
đặc biệt trong lĩnh vực bảo mật thông tin. Vì thế, việc trang bị những
kiến thức cơ bản về số học ngay từ trường phổ thông là hết sức cần
thiết. Không như nhiều ngành khác của toán học, có rất nhiều thành
tựu hiện đại và quan trọng của Số học có thể hiểu được chỉ với những
kiến thức phổ thông được nâng cao một bước. Do đó, đây chính là lĩnh
vực thuận lợi để đưa học sinh tiếp cận nhanh với khoa học hiện đại. Tuy
nhiên, trong chương trình Số học ở trường phổ thông hiện nay, môn Số
học chưa được giành nhiều thời gian. Cũng vì thế mà học sinh thường
rất lúng túng khi giải bài toán Số học, đặc biệt là trong các kì thi chọn
học sinh giỏi.
Trong phần Số học, các hàm số học đóng vai trò quan trọng trong
việc hình thành và nghiên cứu lí thuyết để hoàn thiện. Đây là một vấn

thạc sĩ, nên chắc rằng trong quá trình nghiên cứu không tránh khỏi
những thiếu sót, tôi rất mong được sự đóng góp ý kiến của các Thầy Cô
và độc giả quan tâm tới luận văn này.
Thái Nguyên, ngày 31 tháng 07 năm 2011
Tác giả
Đỗ Cao Sơn
6Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
5
Chương 1
Các hàm số học cơ bản
1.1. Phi - hàm Ơ-le
1.1.1. Định nghĩa
Định nghĩa 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ụ 1.1. ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2, ϕ(4) = 2, ϕ(5) = 4.
Định nghĩa 1.2. Cho n là 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 để a
k
≡ 1(mod n).
Số nguyên dương k bé nhất thỏa mãn a
k
≡ 1(mod n) được gọi là
cấp của số nguyên a (mod n).
Định nghĩa 1.3. 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ụ 1.2. Tập hợp {1, 3, 5, 7} là một hệ thặng dư thu gọn môđulô 8.

, r
2
, , 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

ar
1
, ar
2
, , ar
ϕ(n)

cũng là hệ thặng dư thu gọn môđulô n.
Chứng minh. Trước tiên ta chứng tỏ rằng, mỗi số nguyên ar
j
là nguyên
tố cùng nhau với n. Giả sử ngược lại, (ar
j
, n) > 1 với j nào đó. Khi đó
tồn tại ước nguyên tố p của (ar
j
, n). Do đó, hoặc p |a , hoặc p |r
j
, tức
là hoặc p |a và p |n, hoặc p |r
j
và p |n. Tuy nhiên, không thể có p |r

nguyên với (a, m) = 1. Khi đó a
ϕ(m)
≡ 1 (mo d m).
Chứng minh. Giả sử

r
1
, r
2
, , r
ϕ(n)

là một hệ thặng 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

ar
1
, ar
2
, , ar
ϕ(n)

cũng là
một hệ thặng dư thu gọn môđulô m. Như vậy, các thặng dư dương bé
nhất của ar
1
, ar
2
, , ar

r
ϕ(m)
≡ r
1
r
2
r
ϕ(m)
(mod m).
Vì

r
1
, r
2
, r
ϕ(m)
, m

= 1 nên a
ϕ(m)
≡ 1 (mo d 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 (mo d m).
Vậy a

.m
2
m
k
= m
i
.t
i
với i = 1, 2, , k ta có:
t
n
1
+ t
n
2
+ + t
n
k
≡ (t
1
+ t
2
+ + t
k
)
n
(mod M) với 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ố.
Tính chất 3. Với số nguyên tố p ta có ϕ(p) = p − 1. Ngược lại, nếu p

số nguyên nhỏ hơn p
a
và nguyên
tố cùng nhau với p
a
. Vậy, ϕ(p
a
) = p
a
− p
a−1
.
Ví dụ 1.6. ϕ (125) = ϕ

5
3

= 5
3
−5
2
= 100 ; ϕ

2
10

= 2
10
−2
9

2
2
p
n
k
k
là phân tích n ra thừa số nguyên
tố. Khi đó:
ϕ (n) = n

1 −
1
p
1

1 −
1
p
2



1 −
1
p
k

.
10Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
9

= p
a
j
j

1 −
1
p
j

, j = 1, 2, , k.
Vậy
ϕ (n) = p
a
1
1

1 −
1
p
1

p
a
2
2

1 −
1
p

1 −
1
p
2



1 −
1
p
k

= n

1 −
1
p
1

1 −
1
p
2



1 −
1
p
k

d

.
1.2. Hàm tổng các ước số dương của n
1.2.1. Định nghĩa
Định nghĩa 1.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ụ 1.7. σ(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28.
Chú ý 1.2. Ta có thể biểu diễn hàm σ(n) dưới dạng: σ(n) =

d|n
d
11Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
10
1.2.2. Các tính chất
Bổ đề 1.1. Giả sử m, n là các số nguyên dương nguyên tố cùng nhau.
Khi đó, nếu d là ước chung của mn thì tồn tại cặp duy nhất các ước
dương d
1
của m và d
2
của n sao cho d = d
1
.d
2
. Ngược lại, nếu d
1
và d
2
là các ước dương tương ứng của m và n thì d = d

.
Vì (m, n) = 1 nên tập hợp số nguyên tố p
1
, p
2
, , p
s
và tập hợp các
số nguyên tố q
1
, q
2
, , q
t
không có phần tử chung. Do đó phân tích ra
thừa số của mn có dạng: mn = p
m
1
1
p
m
2
2
p
m
s
s
.q
n
1

q
f
t
t
,
trong đó 0 ≤ e
i
≤ m
i
(i = 1, 2, , s) ; 0 ≤ f
i
≤ n
i
(i = 1, 2, , s).
Đặt: d
1
= p
e
1
1
p
e
2
2
p
e
s
s
, d
2

e
1
1
p
e
2
2
p
e
s
s
trong đó, 0 ≤ e
i
≤ m
i
(i = 1, 2, , s)
d
2
= q
f
1
1
q
f
2
2
q
f
t
t

f
t
t
.
Rõ ràng là ước của mn = p
m
1
1
p
m
2
2
p
m
s
s
.q
n
1
1
q
n
2
2
q
n
t
t
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

a
) = a +1. Mặt khác, σ (p
a
) = 1 +p+ p
2
+ +p
a
=
p
a+1
− 1
p − 1
.
Định lý 1.1. 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). Giả sử (m, n) = 1, ta có:
F (mn) =

d|mn
f(d).
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 tích các ước d
1
của m và d
2
của n và d

) = 1 nên
F (mn) =

d
1
|m
d
2
|n
f(d
1
)f(d
2
) =

d
1
|m
f(d
1
).

d
2
|n
f(d
2
) = F (m).F(n)
Tính chất 1. Hàm σ(n) là hàm nhân tính, tức là: Với mọi số tự nhiên
n

thì σ (n) =
p
α
1
+1
1
− 1
p
1
− 1
.
p
α
2
+1
2
− 1
p
2
− 1

p
α
k
+1
k
− 1
p
k
− 1

α
1
α
0
|
10
Khi ấy
n = α
0
+ 10α
1
+ 10
2
α
2
+ + 10
k−1
α
k−1
+ 10
k
α
k
S(n) = α
0
+ α
1
+ α
2
+ + α

α
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
=

lại m dưới dạng sau đây m = 00 0

(k - s) số 0
β
s
β
s−1
β
1
β
0
|
10
Đặt β
i

=

β
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
α

, m = β
0
suy ra S(n) + S(m) = α
0
+ β
0
Ta có m + n = α
0
+ β
0
, do vậy
S(m + n) =

α
0
+ β
0
nếu α
0
+ β
0
≤ 9
(α
0
+ β
0
− 10) + 1 nếu α
0
+ β
0

α
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
α

; 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
α

) 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
+ β

i=1
S(a
i
)
S(a
1
a
2
a
k
) ≤ S(a
1
).S(a
2
) S(a
k
).
Tính chất 5. 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 = b
1
b
2
b
k
Do đó B = b
k
+ 10b
k−1
+ 10

+ + 10
k−1
Ab
1
≤ S(Ab
k
) + S(10Ab
k−1
) + + S(10
k−1
Ab
1
) (1.2)
Lại theo Tính chất 4, ta có
S(Ab
k
) = S(A + A + + A
  
b
k
số hạng A
) ≤ S(A) + S(A) + + S(A) = b
k
S(A)
16Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
15
Tương tự, ta có
S(10Ab
k−1
) ≤ b

2
+ + b
k
) .S(A)
Do S(B) = b
1
+ b
2
+ + b
k
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ú ý 1.3. Theo nguyên lí quy nạp, ta suy ra kết quả sau:
Nếu A
1
, A
2
, , A
n
là các số nguyên dương thì
S (A
1
A
2
A
n
) ≤ S(A
1
).S(A

+ 1) (α
k
+ 1).
Chứng minh. Được suy ra trực tiếp từ Bổ đề 1.2
17Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
16
1.5. Hàm phần nguyên [x]
1.5.1. Định nghĩa
Định nghĩa 1.1. Hàm phần nguyên [x] của một số nguyên x là số
nguyên lớn nhất không vượt quá x.
Ví dụ 1.9. [2.33] = 2 , [−2.33] = −3
1.5.2. Các tính chất
Tính chất 1. Cho x, y là các số thực, khi đó:
1. [x] ≤ x < x + 1 ; x − 1 < [x] ≤ x ; 0 ≤ x − [x] < 1
2. Với mọi số nguyên m, [x + m] = [x] + m
3. [x] + [ y] ≤ [x + y] ≤ [x] + [y] + 1
4. [x] + [ −x] =

0 nếu x là một số nguyên
−1 nếu trái lại
5. −[−x] là số nguyên nhỏ nhất lớn hơn hoặc bằng x.
6. Nếu m là một số nguyên thì

[x]
m

=

x
m

m

= k. Khi đó, k ≤
x
m
< k + 1 nên km ≤ x < k(m + 1).
Do [x] là số nguyên dương lớn nhất không vượt quá x nên
km ≤ [x] ≤ x < m(k + 1).
Do đó km ≤ [x] < m(k + 1),
suy ra k ≤
[x]
m
< k + 1, tức là

[x]
m

=

x
m

7. Giả sử a, 2a, , na là tất cả các bội số của a nằm trong khoảng [1, m],
ta cần chứng minh [m/a] = n. Thật vậy, do a, 2a, , na là tất cả các
bội số của a nằm trong khoảng [1, m] nên na ≤ m < (n + 1)a. Do đó,
n ≤ m/a < (n + 1). Theo định nghĩa ta có: [m/a] = n.
Định lí được chứng minh.
Tính chất 2 (Công thức Polignac). Cho p là một số nguyên tố, khi
đó số mũ lớn nhất k sao cho p
k


i=1
if
i
. Theo tính chất 1) ta có e
i
=

n
p
i

, f
i
=

n
p
i

−

n
p
i+1

Do đó k =
∞

i=1

Chương 2
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.
2.1. Ứng dụng của Phi - hàm Ơ-le
2.1.1. Xét đồng dư môđulô của một số nguyên tố
Ví dụ 2.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)
Lời giải. 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!(mod p). Suy ra
(p − 1)! ≡ (p − r − 1)!(−1)
r
r! (mod p) ≡ (p − r − 1)! (mod p) . (2.4)
20Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
19
Từ (2.3) và (2.4) suy ra các đồng dư (2.1) và (2.2) là tương đương nhau.
Ví dụ 2.2. Xét dãy U

2.1.2. Chứng minh phép chia với dư
Ví dụ 2.3. Chứng minh rằng: nếu a nguyên tố với 7 thì a
2010
− 1 chia
hết cho 7.
Lời giải. Do 7 là số nguyên tố nên ϕ(7) = 7 - 1 = 6.
Do đó theo định lý Ơ-le ta có a
ϕ(7)
= a
6
≡ 1(mod 7).
Từ đó a
2010
= (a
6
)
335
≡ 1(mod 7) hay a
2010
− 1 ≡ 0(mod 7).
Vậy a
2010
− 1 chia hết cho 7.
Ví dụ 2.4. Chứng minh rằng: 20
15
− 1 chia hết cho 11.31.61
Lời giải.
Chứng minh 20
15
− 1 chia hết cho 11.

với m, n > 1 và (m, n) = 1.
Lời giải. Do (m, n) = 1 nên theo định lí Ơ-le ta có

m
ϕ(n)
≡ 1(mod n)
n
ϕ(m)
≡ 1(mod m)
⇒

m
ϕ(n)
+ n
ϕ(m)
≡ 1(mod n)
n
ϕ(m)
+ m
ϕ(n)
≡ 1(mod m)
Suy ra m
ϕ(n)
+ n
ϕ(m)
≡ 1(mod mn).
2.1.3. Giải phương trình đồng dư
Ví dụ 2.6. Tìm ít nhất 4 nghiệm của phương trình:
x
3

3
≡ 6(mod 30) nên
6
3
+ 25
7
≡ 1(mod 30)
Nếu phân tích 30 = 3 x 10 với (3, 10)=1 thì theo hệ quả (1.1) có
3
ϕ(10)
+ 10
ϕ(3)
≡ 1(mod 30)
Tính toán tương tự trên ta có 3
4
+ 10
3
≡ 1(mod 30)
Vì 3
4
= 81 ≡ 21(mod 30) ; 10
2
≡ 10(mod 30) nên theo hệ quả (1.3) có

3
4

3
+


(mod 210).
Lời giải. Do 210 = 5 x 6 x 7 và (5, 6) = (5, 7) = (6, 7) = 1 nên ta đặt
m
1
= 5, t
1
= 42, m
2
= 6, t
2
= 35, m
3
= 7, t
3
= 30.
Theo hệ quả (1.3) ta có
42
3
+ 35
3
+ 30
3
≡ (42 + 35 + 30)
3
≡ 107
3
(mod 210).
Vậy phương trình có nghiệm (x, y, z, t) là (42, 35, 30, 107).
Nếu phân tích 210 = 3 x 7 x 10 thì tương tự như thế ta thấy phương
trình có nghiệm (x, y, z, t) là (70, 30, 21, 121).

ϕ(b)
− 1

.
.
. b.
Từ đó y
0
là số nguyên. Mặt khác
ax
0
+ by
0
+ c = −aca + ca − c + c = −ca
ϕ(b)
+ ca
ϕ(b)
= 0
Vậy (x
0
, y
0
) là nghiệm riêng của phương trình ax + by + c = 0, suy ra
điều phải chứng minh.
23Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
22
Trở lại phương trình đã cho
12x − 19y + 21 = 0
⇔12x + 19(−y) + 21 = 0
⇔12x + 19z + 21 = 0, với z = −y.


x = −21.12
17
+ 19t
y = −21.
12
18
− 1
19
+ 12t
Nhận xét 2.1. Cách giải này hoàn toàn mang tính chất lí thuyết. Trong
thực tế, chúng ta sẽ không sử dụng cách này.
2.1.5. Tìm cấp của số nguyên
Ví dụ 2.9. Tìm cấp (mod 101) của 2.
Lời giải. Đặt n = 101 và a = 2. Gọi h là cấp của a (mod 101).
Vì 2
ϕ(101)
≡ 1(mod 101) nên ta có
ϕ(101)
.
.
. h (2.6)
Do 101 là số nguyên tố nên dễ thấy ϕ(101) = 101 − 1 = 100. Như vậy
từ (2.6), ta có
101
.
.
. h
24Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
23

≡ 19.196.14 (mo d 101)
≡ (−6)(−6).14 (mo d 101)
≡ 504 (mo d 101)
≡ −1 (mo d 101)
Vì thế ta có
2
50
≡ −1(mod 101) (2.8)
Lại thấy
2
20
≡ 1024
2
≡ 14
2
≡ 196 ≡ −6 (mod 101) (2.9)
Từ (2.7), (2.8) và (2.9) suy ra mâu thuẫn. Vậy giả thiết phản chứng
h < 100 là sai. Vì thế từ 100
.
.
. h suy ra h = 100.
Vậy 100 là cấp (mod 101) của 2.
2.1.6. Tìm số tự nhiên thỏa mãn tính chất hàm số ϕ(n)
Ví dụ 2.10. Tìm tất cả các số tự nhiên n có tính chất n chia hết cho
ϕ(n), trong đó ϕ là hàm Ơ-le.
Lời giải. Hiển nhiên nếu n = 1 thì ϕ(n) |n. Ta xét n > 1. Giả sử n có
phân tích thành thừa số nguyên tố dưới dạng n = p
k
1
1

p
1
p
2
p
i
= x(p
1
− 1)(p
2
− 1) (p
i
− 1).
25Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn