HÀM LEGENDRE VÀ CÁC VẤN ĐỀ LIÊN QUAN LUẬN VĂN THẠC SĨ XUÂT SẮC

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (338.57 KB, 60 trang )

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

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 kết quả nêu trong luận văn là trung thực và chưa từng được công bố
trong bất kỳ công trình nào khác.

Học viên
Phạm Thị Ngọc

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.... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
5. Phương pháp nghiên cứu... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
6. Ý nghĩa khoa học và thực tiễn của đề tài.. . . . . . . . . . . . . . . . . . . . . . . . 2
7. Cấu trúc luận văn... . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
CHƯƠNG 1. CÁC KIẾN THỨC CƠ SỞ . . . . . . . . . . . . . . . . . . . . . 3
1.1. TÍNH CHIA HẾT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... . . 3
1.2. THUẬT TOÁN CHIA... . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .. . . . . . .4
1.3. SỐ NGUYÊN TỐ.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
1.4. ƯỚC CHUNG LỚN NHẤT VÀ THUẬT TOÁN EUCLIDE. . . . . . . . . 7
1.4.1. Ước chung lớn nhất. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.2. Thuật toán Euclide .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .8
1.5. ĐỊNH LÝ BÉZOUT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..9
1.6. ĐỊNH LÝ CƠ BẢN CỦA SỐ HỌC.. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 11
1.7. QUAN HỆ ĐỒNG DƯ VÀ LỚP THẶNG . . . . . . . . . . . . . . . . . . . . . . . . 13

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

việc thường ngày cho đến các tính toán khoa học. Nó là một ngành của
toán học lý thuyết nghiên cứu về tính chất của số nói chung và số nguyên
nói riêng. Những bài toán số học luôn có mặt trong các đề thi chọn học
sinh giỏi toán ở tất cả các cấp học và ở hấu hết các nước trên thế giới.
Hàm Legendre là một trong những hàm cơ bản, đóng vai trò quan trọng
không những trong toán học mà còn nhiều ứng dụng trong lĩnh vực vật lý
và kỹ thuật.
Nhằm tìm hiểu hàm Legendre, ứng dụng của nó và các vấn đề liên quan,
tôi chọn đề tài luận văn thạc sĩ của mình là “Hàm Legendre và các vấn
đề liên quan”.
2. Mục đích nghiên cứu
Tìm hiểu sâu sắc hơn về hàm Legendre và các vấn đề liên quan. Trên cơ
sở đó tìm cách ứng dụng chúng để giải quyết một số bài toán trong chương
trình phổ thông, phục vụ cho việc giảng dạy toán sau này.
3. Nhiệm vụ nghiên cứu
- Nghiên cứu hàm Legendre, hàm ϕ Euler, số nguyên tố, số Fermat, số
Mersenne, và số hoàn hảo.
- Tìm hiểu, nghiên cứu ứng dụng và mối quan hệ giữa các hàm trên.
4. Đối tượng và phạm vi nghiên cứu
Đối tượng và phạm vi nghiên cứu của bản luận văn này gồm khảo sát
hàm Legendre, hàm ϕ Euler và các ứng dụng của chúng đến tập các số
nguyên tố.
5. Phương pháp nghiên cứu
- Nghiên cứu các tài liệu về lý thuyết số có liên quan đến nội dung luận
văn, và các ứng dụng của hàm Legendre, hàm ϕ Euler.
- Nghiên cứu tính chất của hàm Legendre, hàm ϕ Euler, số nguyên tố,

2

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).

1.2. THUẬT TOÁN CHIA
Định lý 1.1. ([1]) Giả sử a, b là các số nguyên và b > 0. Khi đó tồn tại

5

duy nhất các số nguyên q và r sao cho

a = bq + r, 0 ≤ r < b.
Ta gọi q là thương và r là phần dư. Như vậy a chia hết cho b nếu và chỉ
nếu phần dư trong phép chia bằng 0.
Chứng minh.
Ta có


q∈Z



r∈Z
q∈Z
⇔
0≤r0 ≤ r = a − qb < b



a = bq + r

q ∈ Z

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

=

.

1 m−1
2 m−2 2
(x + y)m = xm + Cm
x
y + Cm
x
y + ... + Cnn−1 xy m−1 + y m .

Thay x = 8, y = 1 và m = 2n−1 vào công thức trên, ta được

(8 + 1)2

n−1

= 82

n−1

n−1

⇔(8 + 1)2

n−1

= 4.2. 82

+ 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.

n

Do đó 32 chia cho 4 dư 1, nên 32 + 1 chia cho 4 dư 2 và 32 + 1 chia hết
cho 2.
1.3. SỐ NGUYÊN TỐ
Định nghĩa 1.2. ([7]) Số nguyên p > 1 được gọi là số nguyên tố (hoặc
nguyên tố) nếu không có số nguyên d với d > 1 và d = p để d|p.
Định nghĩa 1.3. ([7]) Số nguyên n > 1 không là số nguyên tố được gọi
là hợp số.

6

Ví dụ 1.4.
2, 3, 5, 7, 11, 13, 17, 19, 23 là các số nguyên tố.
4, 6, 8, 9, 10, 12, 14 là các hợp số.
Nhận xét 1.1.
Số 0 và số 1 không là số nguyên tố cũng không là hợp số.
Tất cả các số nguyên chẵn lớn hơn 2 đều là hợp số, và 2 là số chẵn
duy nhất (và nhỏ nhất) là nguyên tố. Tất cả các số nguyên tố khác 2 là số
lẻ, chúng không chia hết cho 2.
Ta thấy 2 và 3 là hai số nguyên tố liên tiếp duy nhất.
Ví dụ 1.5. Tìm tất cả các số nguyên dương n thỏa mãn 3n − 4, 4n − 5 và

5n − 3 là các số nguyên tố.
Giải. Ta thấy tổng của 3 số trên 3n − 4 + 4n − 5 + 5n − 3 = 12n − 12
là số chẵn, vì vậy có ít nhất một số là số chẵn. Mà số nguyên tố chẵn duy
nhất là số 2. Vì 4n − 5 là số lẻ nên chỉ có 3n − 4 và 5n − 3 có thể là số
chẵn. Giải phương trình 3n − 4 = 2 và 5n − 3 = 2. Ta được kết quả lần
lượt là n = 2 và n = 1. Với n = 2 cả 3 số trên là số nguyên tố.

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 }.

Nên p | p1 p2 ...pm và p | P = (p1 p2 ...pm + 1).
Suy ra p | 1 vô lý.
1.4. ƯỚC CHUNG LỚN NHẤT VÀ THUẬT TOÁN EUCLIDE
1.4.1. Ước chung lớn nhất
Định nghĩa 1.4. ([1]) Ước chung lớn nhất của hai số nguyên a và b không
đồng thời bằng 0 là số nguyên lớn nhất chia hết cả a và b.
Ta dùng kí hiệu (a, b) để chỉ ước chung lớn nhất hai số nguyên a và b.
Nhận xét 1.2.
Ước chung lớn nhất của các số nguyên không đồng thời bằng không

a1 , a2 , ..., an là số nguyên lớn nhất chia hết tất cả các ai , 1 ≤ i ≤ n. Ước
chung lớn nhất của các số nguyên a1 , a2 , ..., an kí hiệu là (a1 , a2 , ..., an ).
(a, b) = (|a|, |b|) = (b, a) (a, b không đồng thời bằng 0) nên ta chỉ
quan tâm đến ước chung lớn nhất của các số nguyên dương.
(a, 0) = |a|, (a = 0).
Cho p là số nguyên tố nếu k là số nguyên dương lớn nhất để pk | n
thì ta kí hiệu là pk ||n .
Ví dụ 1.7. Ước chung của 16 và 64 là ±1, ±2, ±4, ±8. Do đó (16, 64) = 8.
Tương tự (24, 84, 180) = 12, (9, 25) = 1.
Định nghĩa 1.5. ([1]) Các số nguyên a và b không đồng thời bằng 0 được
gọi là nguyên tố cùng nhau nếu (a, b) = 1.

8

Mệnh đề 1.2. ([7])
(a) Nếu p là số nguyên tố, thì (p, m) = p hoặc (p, m) = 1.
(b) Nếu d = (m, n), m = dm , n = dn , thì (m , n ) = 1.
(c) Nếu d = (m, n), m = d m , n = d n , (m n ) = 1, thì d = d.
(d) Nếu d là ước chung của m và n, thì d chia hết (m, n).

(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.

1.4.2. Thuật chia Euclide
Để tìm ước chung lớn nhất của hai số nguyên ta có thể sử dụng thuật
chia Euclide sau đây.
Định lý 1.3 ([1]) (Thuật chia Euclide). Giả sử r0 = a là số nguyên, r1 = b
là số nguyên lớn hơn 0. Ta thực hiện liên tiếp thuật toán chia:
rj = qj+1 rj+1 + rj+2 ,

(1)

với qj+1 , rj+2 là các số nguyên và 0 ≤ rj+2 < rj+1 và nhận được dãy số
giảm r1 > r2 > ... ≥ 0 cho đến khi lần đầu tiên nhận được

rn+1 = 0

9

(2 ≤ n ∈ Z, 0 < rj+2 < rj+1 nếu 0 ≤ j < n − 2). Khi đó (a, b) = rn .
Nói cách khác, (a, b) là phần dư khác 0 cuối cùng trong dãy phép chia
(1).
Chứng minh. Áp dụng liên tiếp thuật toán chia, ta được
r0 = r1 q1 + r2 , 0 < r2 < r1
r1 = r2 q2 + r3 , 0 < r3 < r2
...
rn−2 = rn−1 qn−1 + rn , 0 < rn < rn−1
rn−1 = rn qn + rn+1 , rn+1 = 0.
Chú ý rằng, ta đi đến phép chia với phần dư bằng 0 sau hữu hạn bước, vì

a = r0 > r1 > r2 > ... ≥ 0.
Áp dụng mệnh đề 1.2 (f), ta có (a, b) = (r0 , r1 ) = (r1 , r2 ) = ... =

(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 )
...

Tổng quát

ri = mαi + nβi (với i = 2, ..., k).
Vì ri+1 = ri−1 − ri qi . Suy ra

αi+1 = αi−1 − qi αi
βi+1 = βi−1 − qi βi ,
với i = 3, ..., k −1 Cuối cùng, chúng ta thu được (m, n) = rk = mαk +nβk .
Hay tồn tại số nguyên x = αk , y = βk thỏa mãn mx + ny = (m, n).
Định lý Bézout có thể mở rộng cho nhiều số. Nếu (a1 , a2 , ..., an ) = d
thì tồn tại x1 , x2 , ..., xn thỏa mãn a1 x1 + a2 x2 + ... + an xn = d.
Hệ quả 1.1. ([7]) Nếu a | bc với a, b, c ∈ Z, a = 0 và (a, b) = 1, thì a | c.
Chứng minh. Nếu c = 0 khẳng định trên là đúng. Với c = 0. Từ

(a, b) = 1, theo định lý Bézout tồn tại x, y ∈ Z thỏa mãn ax + by = 1. Do
đó acx + bcy = c. Theo giả thiết a | bc nên a là ước của bcy , mà a là ước
của acx suy ra a | acx + bcy = c.
Hệ quả 1.2. ([1]) Nếu p | a1 a2 ...an , trong đó p là số nguyên tố và
a1 , a2 , ..., an là các số nguyên dương, thì tồn tại i, 1 ≤ i ≤ n sao cho
p | ai .
Hệ quả 1.3. ([7]) Cho a và b là hai số nguyên tố cùng nhau. Nếu c là số
nguyên thỏa mãn a | c và b | c, thì ab | c.
Chứng minh Vì a | c, ta có c = ax với x ∈ Z. Do đó b là ước của ax, vì

11

(a, b) = 1 nên b | x (theo hệ quả 1.1 ). Suy ra x = by , với y ∈ Z, và vì vậy
c = aby hay ab | c.
Hệ quả 1.4. ([7]) Cho p là số nguyên tố, và k là số nguyên với 1 ≤ k < p

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ử

12

p1 < q1 . Như vậy, p1 < qi với mọi i = 1, 2, ..., h (vì các số nguyên tố
trong mỗi biểu diễn được xếp theo thứ tự không giảm). Khi đó, p1 qi
với mọi i. Theo hệ quả 1.2, p1 q1 q2 ...qh = n vô lý. Vậy p1 = q1 và
n/p1 = p2 p3 ...pk = q2 q3 ...qh . Vì n/p1 là số nguyên dương nhỏ hơn n, mà
n là số nguyên dương nhỏ nhất có quá một biểu diễn, nên n/p1 chỉ có thể
biểu diễn dạng tích các số nguyên tố theo một cách duy nhất. Như vậy,
k = h và pi = qi với mọi i. Định lý được chứng minh.
Nhận xét 1.4.
Từ định lý trên, ta có mọi số nguyên n > 1 có thể được viết duy nhất
dưới dạng
n = pα1 1 ...pαk k , với p1 , ..., pk là các số nguyên tố đôi một khác nhau và
α1 , ..., αk là các số nguyên dương. Biểu diễn trên được gọi là phân tích tiêu
chuẩn của n hay biểu diễn chính tắc của n hoặc dạng tiêu chuẩn của n.
Ví dụ 1.9. 1200 = 24 .3.52 .
Bổ đề 1.2. ([1]) Giả sử m, n là các số nguyên dương nguyên tố cùng nhau.
Khi đó, nếu d là một ước dương của mn, thì tồn tại cặp duy nhất các ước
dương d1 của m, d2 của n sao cho d = d1 d2 . Ngược lại, nếu d1 và d2 là các
ước dương tương ứng của m và n, thì d = d1 d2 là một ước dương của mn.
Chứng minh. Giả sử m và 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 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

d = d1 d2 = pe11 pe22 ...pess q1f1 q2f2 ...qtft ,
rõ ràng là ước của
nt
ms n1 n2
1 m2
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 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 ra thừa số nguyên tố của mn.
1.7. QUAN HỆ ĐỒNG DƯ VÀ LỚP THẶNG DƯ
1.7.1. Quan hệ đồng dư
Định nghĩa 1.6. ([1]) Cho m là số nguyên dương, a, b là các số nguyên
ta nói rằng a đồng dư với b theo modulo m nếu m là ước của a − b.
Khi a đồng dư với b modulo m, ta viết a ≡ b (mod m). Nếu a không
đồng dư với b modulo m, ta viết a ≡ b (mod m).
Ví dụ 1.10. 21 ≡ 7 (mod 8) vì 8|(21 − 7) = 16.

−15 ≡ 3 (mod 9) vì 9 | (-15-3)= -18.
32 ≡ 5 (mod 8) vì 8 (32 − 5) = 27.
Dễ thấy các khẳng định sau đây là tương đương:
1. a ≡ b (mod m)
2. m | (a − b)
3. a = b + km với k ∈ Z.
Định lý 1.6. ([1]) Quan hệ đồng dư modulo m là một quan hệ tương
đương trên tập Z, tức là có các tính chất:

14

(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 .

Hệ quả 1.6. ([1]) Giả sử a ≡ b (mod m1 ), a ≡ b (mod m2 ), ..., a ≡ b
(mod mk ), trong đó a, b là các số nguyên và m1 , m2 , ..., mk là các số nguyên

15

dương nguyên tố cùng nhau từng cặp. Khi đó

a ≡ b (mod m1 , ..., mk ),
1.7.2. Lớp thặng dư (Residue classes)
Từ định lý 1.6, quan hệ đồng dư là quan hệ tương đương trên tập các
số nguyên vì thế nó phân chia tập Z thành m lớp thặng dư modulo m.
Mỗi lớp chỉ gồm các số có cùng số dư khi chia cho m.
Định nghĩa 1.7. ([7] Một tập gồm các phần tử có cùng số dư khi chia
cho m gọi là một lớp thặng dư modulo m.
Ví dụ 1.11. Với m = 4 có 4 lớp thặng dư modulo 4

{..., −8, −4, 0, 4, 8, ...}
{..., −7, −3, 1, 5, 9, ...}
{..., −6, −2, 2, 6, 10, ...}
{..., −5, −1, 3, 7, 11, ...}
Định nghĩa 1.8. ([3]) Một tập hợp m số nguyên a1 , a2 , ..., am được gọi là
một hệ thặng dư đầy đủ modulo m nếu với i = j thì ai ≡ aj (mod m).
Ví dụ 1.12 {5, 7, 9, 10, 14, 18} là hệ thặng dư đầy đủ modulo 6.
Mệnh đề 1.3. ([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à cho b là một số nguyên. Giả sử rằng S là
một hệ thặng dư đầy đủ modulo m. Thì tập hợp

T = aS + b = {as + b|s ∈ S}
cũng là một hệ thặng dư đầy đủ modulo m.

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

tại số nguyên x thỏa mãn ax ≡ 1 (mod m).
Ta gọi x là nghịch đảo của a modulo m, ký hiệu là a−1 hoặc a1 (mod m).
Vì tất cả các nghịch đảo cùng thuộc một lớp thặng dư modulo m, nghịch
đảo của a được xác định là duy nhất modulo m cho tất cả các số nguyên
tố cùng nhau với m.
Định lý 1.10 ( Định lý Wilson’s, ([7])). Với mọi số nguyên tố p, ta có
(p − 1)! ≡ −1 (mod p).
Chứng minh:
Định lý đúng trong trường hợp p = 2, 3.
Ta xét trường hợp p ≥ 5. Gọi S = {2, 3, ..., p − 2}. Do p là số nguyên
tố nên với mỗi số s ∈ S có duy nhất nghịch đảo s ∈ {1, 2, ..., p − 1}. Mà

17

s = 1 và s = p − 1 nên s ∈ S . Hơn nữa s = s , nếu không thì s2 ≡ 1
(mod p) suy ra p | (s − 1) và p | (s + 1) vô lý vì s + 1 < p. Như vậy, ta
p−3
có thể nhóm các phần tử của S thành
cặp (s, s ) thỏa mãn ss ≡ 1
2
(mod p). Do đó
2.3...(p − 3)(p − 2) ≡ 1 (mod p).
Nhân hai vế với 1 và (p − 1) ta được

(p − 1)! ≡ 1.(p − 1) ≡ −1 (mod p).rule1.6ex1.6ex
Mệnh đề đảo của định lý Wilson cũng đúng.
Định lý 1.11. ([1]) Giả sử n là số nguyên dương sao cho (n − 1)! ≡ −1
(mod n). Khi đó n là số nguyên tố. .
Chứng minh.

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 ).

Chứng minh.
Vì i = j nên pi , pj là các số nguyên tố khác nhau, suy ra (pα1 1 , pα2 2 ...pαk k ) =
1 và f là hàm nhân tính, suy ra
f (n) = f (pα1 1 ).f (pα2 2 pα3 3 ...pαk k ).
Tương tự (pα2 2 , pα3 3 ...pαk k ) = 1 nên

f (pα2 2 pα3 3 ...pαk k ) = f (pα2 2 ).f (pα3 3 ...pαk k ).
Tiếp tục như vậy, ta được

f (n) = f (pα1 1 ).f (pα2 2 )...f (pαk k ).

19

Định nghĩa 2.3. Hàm số học µ được gọi là hàm Mobius nếu

1 nếu n = 1
µ(n) = 0 nếu p2 |n với số nguyên tố p > 1

(−1)k nếu n = p1 ...pk , với p1 , ..., pk là các số nguyên tố khác nhau.
Ví dụ 2.2. µ(2) = −1, µ(6) = 1, µ(12) = µ(22 .3) = 0.
Định nghĩa 2.4. Hàm tổng các ước dương, kí hiệu là σ được xác định bởi
: σ(n) bằng tổng mọi ước dương của n

d.

σ(n) =
0
Ví dụ 2.3. σ(1) = 1, σ(2) = 3, σ(3) = 4, σ(4) = 7, σ(5) = 6.

Đị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
Ví dụ 2.4. τ (1) = 1, τ (2) = 2, τ (3) = 2, τ (4) = 3.
Bổ đề 2.1 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 dương của pa là 1, p, p2 , ..., pa . Do đó

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

pa+1 − 1
.
p−1

Định lý 2.2. Hàm Mobius µ là nhân tính
Chứng minh.

Giả sử m, n là số nguyên dương thỏa mãn (m, n) = 1.
Nếu m = n = 1 thì µ(1) = 1. Suy ra µ(mn) = 1 = 1.1 = µ(m)µ(n).
Nếu p2 |m với p > 1, thì p2 |mn và do đó µ(m) = µ(mn) = 0, suy
ra µ(mn) = µ(m)µ(n) = 0. Bây giờ xét m = p1 ...pk , n = q1 ...qh , ở

20

đây p1 , ..., pk , q1 , ..., qh là số nguyên tố khác nhau (vì (m, n) = 1). Thì

µ(m) = (−1)k , µ(n) = (−1)h , và mn = p1 ...pk q1 ...qh . Nó suy ra µ(mn) =
(−1)k+h = (−1)k (−1)h = µ(m)µ(n).
Định lý 2.3.
1, nếu n = 1,
µ(d) =
0, nếu n > 1.
d|n

Chứng minh.
Nếu n = 1 thì

µ(d) = 1.

d|n

Nếu n > 1 gọi n = pα1 1 pα2 2 ...pαmm là phân tích tiêu chuẩn của n. Ước d của

n mà µ(d) = 0 có dạng
1, p1 , ..., pm , pi pj (i < j), pi pj pk (i < j < k), ..., p1 p2 ...pm .
Suy ra

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

µ(pi ) +
i

µ(pi pj ) + ... + µ(p1 p2 ...pm )
i
Vậy
1
2
3
m
µ(d) = 1+(−1)1 Cm
+(−1)2 Cm
+(−1)3 Cm
...+(−1)m Cm
= (1−1)m = 0.
d|n

Định nghĩa 2.6. Cho f là hàm số học. Hàm tổng F được xác định bởi:

F (n) =

f (d).
d|n

Định lý 2.4. Nếu f là hàm nhân tính, thì F cũng là hàm nhân tính.

Chứng minh Giả sử m và n là số nguyên dương nguyên tố cùng nhau và
giả sử 0 < d là ước của mn. Theo bổ đề 1.2 thì d có thể được biểu diễn
duy nhất là d = kh, ở đây k|m và h|n.

HÀM LEGENDRE VÀ CÁC VẤN ĐỀ LIÊN QUAN LUẬN VĂN THẠC SĨ XUÂT SẮC

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về