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

PHẠM THỊ NGỌC

HÀM LEGENDRE
VÀ CÁC VẤN ĐỀ LIÊN QUAN

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

Đà Nẵng - Năm 2013


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

PHẠM THỊ NGỌC

HÀM LEGENDRE
VÀ CÁC VẤN ĐỀ LIÊN QUAN

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. CAO VĂN NUÔI

Đà Nẵng - Năm 2013

1.7.1. Quan hệ đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.2. Lớp thặng dư (Residue classes) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
CHƯƠNG 2. HÀM LEGENDRE VÀ CÁC VẤN ĐỀ LIÊN QUAN
.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1. HÀM NHÂN TÍNH .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18
2.2. HÀM ϕ EULER .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3. ĐỊNH LÝ EULER VÀ ĐỊNH LÝ NHỎ CỦA FERMAT .. . . .. . . . . . . 24
2.4. HÀM FLOOR .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5. HÀM LEGENDRE .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29
2.6. SỐ FERMAT .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31
2.7. SỐ MERSENNE .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34


2.8. SỐ HOÀN HẢO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37
CHƯƠNG 3. CÁC ỨNG DỤNG CỦA HÀM LEGENDRE VÀ
CÁC VẤN ĐỀ LIÊN QUAN .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1. CÁC BÀI TOÁN LIÊN QUAN ĐẾN HÀM LEGENDRE. . . . . . . . . .39
3.2. CÁC BÀI TOÁN LIÊN QUAN ĐẾN HÀM ϕ EULER . . . . . . . . . . . . 45
3.3. CÁC BÀI TOÁN VỀ CÁC SỐ NGUYÊN TỐ .. . . . . . . . . . . . . . . . . . . 49
KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
DANH MỤC TÀI LIỆU THAM KHẢO .. . . . . . . . . . . . . . . . . . . . . .55
QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN THẠC SĨ (bản sao)


1

MỞ ĐẦU
1. Lí do chọn đề tài
Có thể nói, lý thuyết số là một trong những ngành toán học lâu đời
nhất, được hầu hết mọi người sử dụng ở nhiều mức độ khác nhau từ công

từ đó áp dụng cụ thể vào việc giải quyết một số bài toán số học đặc biệt.
6. Ý nghĩa khoa học và thực tiễn của đề tài
Xây dựng một giáo trình có tính hệ thống với thời lượng thu gọn, có
thể dạy được cho các học sinh chuyên toán bậc trung học phổ thông.
Xây dựng một hệ thống các bài toán.
7. Cấu trúc luận văn
Luận văn được chia thành ba chương:
Chương 1: Các kiến thức cơ sở
Trình bày các kiến thức cơ sở liên quan như tính chia hết, số nguyên tố
và định lý cơ bản của số học, quan hệ đồng dư và lớp thặng dư, ... làm cơ
sở để xây dựng lý thuyết về hàm Legendre và các vấn đề liên quan.
Chương 2. Hàm Legendre và các vấn đề liên quan
Chương này trình bày khá đầy đủ lý thuyết về hàm nhân tính, hàm ϕ
Euler, định lý Euler và định lý nhỏ Fermat, hàm Floor, hàm Legendre, số
Fermat, số Mersenne và số hoàn hảo. Trong từng phần đều có các ví dụ
minh họa cụ thể.
Chương 3. Các ứng dụng của hàm Legendre và các vấn đề liên quan
Chương này áp dụng lý thuyết của chương hai để giải một số bài toán
và được chia làm ba dạng: các bài toán liên quan đến hàm Legendre, các
bài toán liên quan đến hàm ϕ Euler và các bài toán về các số nguyên tố.


3

CHƯƠNG 1
CÁC KIẾN THỨC CƠ SỞ
1.1. TÍNH CHIA HẾT
Định nghĩa 1.1. ([7]) Giả sử a, b là các số nguyên và a = 0. Ta nói a chia
hết b (hoặc b chia hết cho a hoặc a là ước của b) nếu tồn tại số nguyên c
sao cho b = ac.


k3 a − b = k3 a − ka = (k3 − k)a, với k3 − k ∈ Z suy ra c = ±(k − k3 )a,
với ±(k − k3 ) ∈ Z. Hay a | c.
(f) Vì a | b và b | a do đó a = 0 và b = 0. Do (c) ta có |b| ≥ |a| và
|a| ≥ |b|. Suy ra |a| = |b|.
(g) Ta có ab = k = 0 ∈ Z. Vậy b = a.k, k = 0 hay k | b.
Tập hợp các số nguyên, ký hiệu bởi Z có thể phân chia thành hai tập
hợp con, tập các số nguyên lẻ và tập các số nguyên chẵn:
{±1, ±3, ±5, ...} và {0, ±2, ±4, ...} .
Tập các số nguyên lẻ và chẵn tạo nhiều thuận tiện trong việc giải quyết
những vấn đề khác nhau trong lý thuyết số. Sau đây là một số khái niệm
cơ bản:
(1) Một số lẻ là số có dạng 2k + 1, với k ∈ Z ;
(2) Một số chẵn là số có dạng 2m, với m ∈ Z ;
(3) Tổng của hai số lẻ là một số chẵn;
(4) Tổng của hai số chẵn là một số chẵn;
(5) Tổng của một số lẻ và một số chẵn là một số lẻ;
(6) Tích của hai số lẻ là một số lẻ;
(7) Một tích của các số nguyên là chẵn nếu và chỉ nếu có ít nhất một
thừa số là số chẵn.
Ví dụ 1.2.
Cho số nguyên n >1. Chứng minh rằng
(a) 2n là tổng của hai số nguyên lẻ liên tiếp;
(b) 3n là tổng của ba số nguyên liên tiếp.
Chứng minh:
(a) Ta có 2n = (2k − 1) + (2k + 1) với k = 2n−2 ta thu được 2n =

(2n−1 − 1) + (2n−1 + 1).
(b) Ta có 3n = (s − 1) + s + (s + 1) với s = 3n−1 ta thu được
3n = (3n−1 − 1) + 3n−1 + (3n−1 + 1).

q = ab
⇔ r = a − qb
⇔
r = a − qb.
a
a
b −1< q ≤ b

Vậy ta có điều phải chứng minh.
n

Ví dụ 1.3. Cho số nguyên dương n. Chứng minh rằng 32 + 1 chia hết
cho 2 nhưng không chia hết cho 4.
n

n

n

n−1

Giải. Ta có, 32 là số lẻ và 32 + 1 là số chẵn. Ta có 32 = (32 )2

92

n−1

= (8 + 1)2

n−1


+ C21n−1 82
n−1

n

−1

−1

n−1

+ C22n−1 82
n−1

+ C21n−1 82
n

−2

−2

+ ... + Cnn−1 8 + 1
n−1

+ C22n−1 82

−3

+ ... + Cnn−1 + 1.

Ví dụ 1.6. [AHSME 1976] Cho p và q là hai số nguyên tố và x2 −px+q = 0
có hai nghiệm dương phân biệt. Tìm p và q .
Giải. Giả sử x1 , x2 với x1 < x2 , là hai nghiệm nguyên dương phân biệt.
Thì x2 − px + q = (x − x1 )(x − x2 ) suy ra p = x1 + x2 và q = x1 .x2 . Vì
q là số nguyên tố, nên x1 = 1 do đó q = x2 và p = x2 + 1. p, q là hai số
nguyên tố liên tiếp, suy ra q = 2 và p = 3.
Bổ đề 1.1. ([1]) Mỗi số nguyên lớn hơn 1 đều có ước nguyên tố.
Để chứng minh Bổ đề 1.1 ta nhắc lại nguyên lý sau
Nguyên lý sắp thứ tự tốt. Mỗi tập không rỗng các số nguyên dương
đều có phần tử bé nhất.
Chứng minh bổ đề 1.1. Giả sử tồn tại số nguyên lớn hơn 1 không có
ước nguyên tố nào. Gọi A là tập hợp chứa các số như vậy, theo giả thiết
phản chứng A khác rỗng. Nên từ nguyên lý sắp thứ tự tốt suy ra tồn tại
n là số nhỏ nhất thuộc A. Vì n là ước của chính nó, mà theo giả thiết, n
không có ước nguyên tố, nên n không phải là số nguyên tố. Vì thế n là


7

hợp số, ta có n = ab, 1 < a < n, 1 < b < n. Vì a < n nên a phải có ước
nguyên tố. Theo mệnh đề 1.1 (b), mọi ước của a đều là ước của n, nên n
có ước nguyên tố (mâu thuẫn).
Định lý 1.2. ([7]) Có vô số số nguyên tố.
Chứng minh. Bằng phương pháp phản chứng, ta giả sử có hữu hạn số
nguyên tố: p1 < p2 < ... < pm .
Xét P = p1 p2 ...pm + 1.
Nếu P là một số nguyên tố thì P > pm , mâu thuẫn với giả sử pm là
số nguyên tố lớn nhất. Nên P là hợp số, suy ra có một số nguyên tố p > 1
là ước của P ,
suy ra p ∈ {p1 , p2 , ..., pm }.

(e) Nếu px ||m và py ||n, thì pmin{x,y} ||(m, n). Hơn nữa, nếu m =

pα1 1 ...pαk k và n = pβ1 1 ...pβk k , αi , βi ≥ 0, i = 1, ..., k , thì
min{α1 ,β1 }

(m, n) = p1

min{αk ,βk }

...pk

(f) Nếu m = nq + r, thì (m, n) = (n, r).
(g) Nếu ((m, n), p) = (m, (n, p)) = d thì (m, n, p) = d;
(h) Nếu d | ai , i = 1, ..., s, thì d|(a1 , ..., as );
(i) Nếu ai = pα1 1i ...pαk ki , i = 1, ..., s, thì
min{α11 ,...,α1k }

(a1 , ..., as ) = p1

min{αk1 ,...,αkk }

...pk

Nhận xét 1.3.

a1 , a2 , ..., an là nguyên tố cùng nhau nếu (a1 , a2 , ..., an ) = 1.
(a1 , a2 , ..., an ) = 1 không suy ra (ai , aj ) = 1 với 1 ≤ i < j ≤ n.
Ví dụ, ta có (2, 3, 6) = 1 nhưng (2, 6) = 2.
Nếu a1 , a2 , ..., an thỏa mãn (ai , aj ) = 1 với 1 ≤ i < j ≤ n, ta nói
a1 , a2 , ..., an là các số nguyên tố cùng nhau.


(rn−1 , rn ) = (rn , 0) = rn . Vậy (a, b) = rn , phần dư khác không cuối cùng.
Ví dụ 1.8. Tìm ước chung lớn nhất của 994 và 2012.
Giải.
Từ thuật chia Euclide ta có
2012 = 994.2 + 24
994 = 24.41 + 10
24 = 10.2 + 4
10 = 4.2 + 2
4 = 2.2 + 0.
Vậy (994,2012)=2.
1.5. ĐỊNH LÝ BÉZOUT
Định lý 1.4 (Bézout, ([7])). Giả sử m, n là hai số nguyên dương, khi đó
tồn tại các số nguyên x và y thỏa mãn mx + ny = (m, n).


10

Chứng minh. Đặt r0 = m, r1 = n. Từ thuật chia Euclide ta có

r0 = r1 q1 + r2
r1 = r2 q2 + r3
r2 = r3 q3 + r4
...
Suy ra

r2 = r0 − r1 q1
r3 = −r0 q2 + r1 (1 + q1 q2 )
r4 = r0 (1 + q2 q3 ) − r1 (q1 + q3 − q1 q2 q3 )
...

thì p | Cpk .
Chứng minh: Ta có
k−1
kCpk = pCp−1
suy ra p là ước của kCpk . Vì (p, k) = 1 theo hệ quả 1.1 suy ra p | Cpk .
1.6. ĐỊNH LÝ CƠ BẢN CỦA SỐ HỌC
Định lý 1.5 (Định lý cơ bản của số học, ([1])). Mọi số nguyên lớn hơn 1
đều biểu diễn được một cách duy nhất dưới dạng tích các thừa số nguyên
tố, trong đó các thừa số được viết theo thứ tự không giảm.
Chứng minh. Chứng minh bất kỳ số nguyên n > 1 có thể biểu diễn
thành tích của các thừa số nguyên tố:
Giả sử p1 là một ước nguyên tố của n.
Nếu p1 = n thì n = p1 là một thừa số nguyên tố của n.
Nếu p1 < n thì n = p1 r1 , với r1 > 1.
Nếu r1 là một số nguyên tố, thì n = p1 p2 (với p2 = r1 ) là thừa số cần tìm
của n.
Nếu r1 là hợp số, thì r1 = p2 r2 , với p2 là số nguyên tố, r2 > 1, và như
thế n = p1 p2 r2 . Nếu r2 là số nguyên tố, thì n = p1 p2 p3 , với r2 = p3 , ta
tìm được thừa số nguyên tố của n. Nếu r2 là hợp số, thì chúng ta tiếp tục
thuật toán này, ta thu được một dãy các số nguyên r1 > r2 > ... ≥ 1. Sau
hữu hạn bước ta tìm được rk = 1 khi đó n = p1 p2 ...pk .
Chứng minh biểu diễn trên là duy nhất. Giả sử rằng tồn tại số nguyên
lớn hơn 1 có hai cách biểu diễn dưới dạng tích các thừa số nguyên tố. Gọi

n là số nhỏ nhất trong các số đó và n có hai cách biểu diễn:
n = p1 p2 ...pk = q1 q2 ...qh
trong đó p1 , p2 , ...pk , q1 , q2 , ..., qh là các số nguyên tố, p1 ≤ p2 ≤ ... ≤ pk và

q1 ≤ q2 ≤ ... ≤ qh .
Trước tiên, ta sẽ chỉ ra rằng p1 = q1 . Không giảm tổng quát, ta giả sử

Vì (m, n) = 1 nên tập hợp các 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ố nguyên tố của mn có dạng:
nt
ms n1 n2
1 m2
mn = pm
1 p2 ...ps q1 q2 ...qt .

Như vậy, nếu d là một ước dương của mn thì

d = pe11 pe22 ...pess q1f1 q2f2 ...qtft ,
trong đó 0 ≤ ei ≤ mi (i = 1, 2, ..., s); 0 ≤ fj ≤ nj (j = 1, 2, ..., t). Đặt

d1 = pe11 pe22 ...pess ,


13

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 ...pess ,
trong đó 0 ≤ ei ≤ mi (i = 1, 2, ..., s), và

d2 = q1f1 q2f2 ...qtft ,
trong đó 0 ≤ fj ≤ nj (j = 1, 2, ..., t). Số nguyên



(a) Tính phản xạ: a ≡ a (mod m);
(b) Tính đối xứng: Nếu a ≡ b (mod m) thì b ≡ a (mod m);
(c) Tính bắc cầu: Nếu a ≡ b (mod m) và b ≡ c (mod m), thì a ≡ c
(mod m).
Chứng minh:
a) Ta có a ≡ a (mod m) vì m | (a − a) = 0.
b) Nếu a ≡ b (mod m) tức là m | (a − b). Khi đó, m | (b − a) và b ≡ a
(mod m).
c) Nếu a ≡ b (mod m), b ≡ c (mod m) thì m | (a − b) và m | (b − c).
Do đó, m | (a − b + b − c) hay m | (a − c) nên a ≡ c (mod m).
Định lý 1.7. ([1]) Giả sử a, b, c, d, m là các số nguyên, m > 0, a ≡ b (mod

m), c ≡ d (mod m). Khi đó:
1. a + c ≡ b + d (mod m),
2. a − c ≡ b − d (mod m),
3. ac ≡ bd (mod m).
Hệ quả 1.5. ([1]) Giả sử a, b, c và m là các số nguyên, m > 0 và a ≡ b
(mod m). Khi đó:
1. a + c ≡ b + c (mod m),
2. a − c ≡ b − c (mod m),
3. ac ≡ bc (mod m),
4. ak ≡ bk (mod m), với k ∈ N∗ .
Định lý 1.8. ([1]) Nếu a, b, c, m là các số nguyên m > 0, (c, m) = 1 và
ac ≡ bc (mod m). Khi đó a ≡ b (mod m).
Định lý 1.9. ([1]) Giả sử a ≡ b (mod m1 ), a ≡ b (mod m2 ), ..., a ≡ b
(mod mk ), trong đó a, b, m1 , ..., mk là các số nguyên và m1 , m2 , ..., mk > 0.
Khi đó
a ≡ b (mod [m1 , ..., mk ]),
trong đó [m1 , ..., mk ] là bội chung nhỏ nhất của m1 , m2 , ..., mk .

Chứng minh.
Giả sử S = {s1 , s2 , ..., sm } là một hệ thặng dư đầy đủ modulo m. Ta
chứng minh T = {as1 + b, as2 + b, ..., asm + b} cũng là một hệ thặng dư
đầy đủ modulo m.
Ta cần chứng minh rằng với 1 ≤ i = j ≤ m thì asi + b ≡ asj + b
(mod m). Thật vậy, nếu asi + b ≡ asj + b (mod m) thì asi ≡ asj (mod


16

m). Vì (a, m) = 1 nên theo định lý 1.8 ta có si ≡ sj (mod m). Vô lý vì
với 1 ≤ i = j ≤ m thì si ≡ sj .
Vậy T = {as1 + b, as2 + b, ..., asm + b} cũng là một hệ thặng dư đầy
đủ.
Mệnh đề 1.4. ([7]) Cho m là một số nguyên dương. Cho a ∈ Z là một số
nguyên tố cùng nhau với m, và b là một số nguyên. Tồn tại số nguyên x
sao cho ax ≡ b (mod m), và tất cả các số nguyên này cùng thuộc một lớp
thặng dư modulo m.
Chứng minh:
Cho {c1 , c2 , ..., cm } là một hệ thặng dư đầy đủ modulo m. Do mệnh
đề 1.3,
{ac1 − b, ac2 − b, ..., acm − b}
cũng là một hệ thặng dư đầy đủ. Do đó tồn tại ci để aci − b ≡ 0 (mod m)
giả sử ac1 − b ≡ 0 (mod m) hoặc c1 là một nghiệm của phương trình đồng
dư ax ≡ b (mod m).
Mặt khác, nếu cả x và x thỏa mãn phương trình đồng dư, ta có

ax ≡ ax (mod m). do (a, m) = 1 nên theo định lý 1.8 ta có x ≡ x (mod
m).
Đặc biệt, với b = 1 theo mệnh đề 1.4 ta có: nếu (a, m) = 1, thì tồn

Giả sử ngược lại, n là hợp số và (n − 1)! ≡ −1 (mod n). Vì n là
hợp số, ta có n = ab, trong đó 1 < a < n và 1 < b < n. Khi đó,

a | (n − 1)!. Mặt khác, do (n − 1)! ≡ −1 (mod n) nên n | [(n − 1)! + 1],
suy ra a | [(n − 1)! + 1]. Như vậy, a | (n − 1)! và a | [(n − 1)! + 1] nên
a | 1 mâu thuẫn.
Định lý cho chúng ta cách khác để xác định một số có là số nguyên
tố hay không. Tuy nhiên, nó rất khó thực hiện khi n có giá trị lớn.


18

CHƯƠNG 2
HÀM LEGENDRE VÀ CÁC VẤN ĐỀ LIÊN
QUAN
2.1. HÀM NHÂN TÍNH
Định nghĩa 2.1. Hàm số học là hàm xác định trên tập hợp các số nguyên
dương.
Định nghĩa 2.2. Hàm số học f được gọi là hàm nhân tính nếu f (mn) =

f (m)f (n) khi m, n là các số nguyên dương nguyên tố cùng nhau.
Hàm f gọi là hàm nhân tính hoàn toàn nếu f (mn) = f (m)f (n), với mọi
số nguyên dương m, n.
Nhận xét 2.1. Hàm nhân tính hoàn toàn là hàm nhân tính.
Ví dụ 2.1. Hàm f (n) = n với mọi n nguyên dương là hàm nhân tính
hoàn toàn, vì f (mn) = mn = f (m)f (n).
Và hàm f (n) = n cũng là hàm nhân tính.
Hàm f (n) = 1 là hàm nhân tính.
Định lý 2.1. Giả sử n = pα1 1 pα2 2 ...pαk k là phân tích ra thừa số nguyên tố
của n, và f là hàm nhân tính. Khi đó f (n) = f (pα1 1 ).f (pα2 2 )...f (pαk k ).

Định nghĩa 2.5. Hàm số các ước dương, kí hiệu là τ , được xác định bởi:

τ (n) bằng số các ước dương của số nguyên dương n
τ (n) =

1.
0

µ(d) = µ(1) +
d|n

µ(pi ) +
i

µ(pi pj ) + ... + µ(p1 p2 ...pm )
i