TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2

KHOA TOÁN

Ngô Thị Vân

SỐ NGUYÊN TỐ VÀ ỨNG DỤNG

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC

Hà Nội – Năm 2016


TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2

KHOA TOÁN

Ngô Thị Vân

SỐ NGUYÊN TỐ VÀ ỨNG DỤNG
Chuyên ngành: Đại số

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC
Thạc sỹ: Dương Thị Luyến

Hà Nội – Năm 2016


i

Lời cảm ơn

Tôi xin chân thành cảm ơn sự giúp đỡ của các thầy cô giáo trong tổ đại số,
các thầy cô trong khoa Toán, các thầy cô giáo trong trường ĐHSP Hà Nội
2 và các bạn sinh viên. Đặc biệt em xin được bày tỏ lòng biết ơn sâu sắc
của mình tới cô Dương Thị Luyến - người đã tận tình giúp đỡ em trong
quá trình hoàn thành khóa luận của mình.Do lần đầu tiên làm quen với
công tác nghiên cứu khoa học. Hơn nữa do thời gian có hạn và năng lực
của bản thân còn hạn chế nên không tránh khỏi những thiếu sót. Em xin
kính mong được sự đóng góp ý kiến của các thầy cô và các bạn sinh viên
để khóa luận của em được hoàn thiện và có nhiều ứng dụng trong thực tế.
Em xin chân thành cảm ơn!

Hà Nội, ngày 12 tháng 5 năm 2016
Sinh viên
Ngô Thị Vân


Khóa luận tốt nghiệp Đại học

Ngô Thị Vân

Lời cam đoan

Tôi xin khẳng định rằng đây là công trình nghiên cứu khoa học của tôi do
bản thân tôi đã nghiên cứu và hoàn thành trên cơ sở những kiến thức đã
được học và tài liệu tham khảo.

Hà Nội, ngày 12 tháng 5 năm 2016

Sinh viên
Ngô Thị Vân

i


Mục lục

Lời mở đầu

1

1 SỐ NGUYÊN TỐ

3

1.1

1.2

1.3

1.4

Sơ lược các giai đoạn phát triển của lý thuyết số nguyên tố

3

1.1.1


Giai đoạn 1(Trước công nguyên) . . . . . . . . . .

3

1.1.2

Giai đoạn 2 (Trước thế kỉ 17) . . . . . . . . . . .

4

1.1.3

Giai đoạn 3 (Sau thế kỉ 17) . . . . . . . . . . . .

4

Định nghĩa và tính chất . . . . . . . . . . . . . . . . . .

5

1.2.1

Định nghĩa . . . . . . . . . . . . . . . . . . . . .

5

1.2.2

Tính chất . . . . . . . . . . . . . . . . . . . . . .


6

Một số định lý cơ bản của số học . . . . . . . . . . . . .

8

1.3.1

Định lý Euclid

. . . . . . . . . . . . . . . . . . .

8

1.3.2

Định lý cơ bản của số học . . . . . . . . . . . . .

8

1.3.3

Dạng phân tích tiêu chuẩn . . . . . . . . . . . . .

9

1.3.4

Một số ứng dụng của định lý cơ bản . . . . . . .


10

Một số định lý nổi tiếng về số nguyên tố . . . . . . . . .

14

1.4.1

Định lý Wilson . . . . . . . . . . . . . . . . . . .

14

1.4.2

Định lý Fermat nhỏ . . . . . . . . . . . . . . . . .

16

1.4.3

Định lý Korelt . . . . . . . . . . . . . . . . . . . .

18

ii


Khóa luận tốt nghiệp Đại học

1.4.4

1.5

1.6

Ngô Thị Vân

Một số định lý khác về số nguyên tố . . . . . . .

19

Bảng các số nguyên tố . . . . . . . . . . . . . . . . . . .

19

1.5.1

Sàng Eratosthène . . . . . . . . . . . . . . . . . .

19

1.5.2

Sự phân bố số nguyên tố . . . . . . . . . . . . . .

21

Kiểm tra số nguyên tố . . . . . . . . . . . . . . . . . . .

24


1.6.1

Các phương pháp thô sơ . . . . . . . . . . . . . .

24

1.6.2

Kiểm tra theo xác suất . . . . . . . . . . . . . . .

25

1.6.3

Các phép kiểm tra bất định . . . . . . . . . . . .

25

1.6.4

Các phương pháp lý thuyết số . . . . . . . . . . .

26

2 Một số bài tập áp dụng
2.1

27

Các bài toán về tập hợp số nguyên tố . . . . . . . . . . .


27

2.1.1

Loại 1. Tìm tập hợp số nguyên tố . . . . . . . . .

27

2.1.2

Loại 2.Các bài toán áp dụng định lý cơ bản của số
học, định lý Fermat . . . . . . . . . . . . . . . . .

30

2.2

Nhận biết số nguyên tố . . . . . . . . . . . . . . . . . . .

35

2.3

Chứng minh một số, một biểu thức cho trước là số nguyên
tố . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

2.4


Tìm số nguyên tố thỏa mãn điều kiện cho trước . . . . .

39

2.5

Một số bài tập dạng khác . . . . . . . . . . . . . . . . .

45

3 Ứng dụng số nguyên tố trong lý thuyết mật mã

50

3.1

Hệ mã mũ . . . . . . . . . . . . . . . . . . . . . . . . . .

51

3.2

Hệ mã RSA . . . . . . . . . . . . . . . . . . . . . . . . .

54

3.2.1

Cơ sở xây dựng thuật toán RSA . . . . . . . . . .


54

3.2.2

Thuật toán RSA . . . . . . . . . . . . . . . . . .

55

iii


Khóa luận tốt nghiệp Đại học

Ngô Thị Vân

Kết luận

59

Tài liệu tham khảo

59

iv


Khóa luận tốt nghiệp Đại học

Ngô Thị Vân


Lời mở đầu
1. Lý do chọn đề tài
Đại số và số học là một bộ phận quan trọng đối với Toán học. Từ rất
lâu, các bài toán số học đã làm say mê nhiều người, từ những nhà toán
học lỗi lạc mọi thời đại tới đông đảo bạn đọc yêu toán. Vấn đề số nguyên
tố là một trong những vấn đề trung tâm của số học, nó đã chiếm mất
khoảng thời gian hàng nghìn năm của các nhà toán học các thời đại.
Không ở đâu như trong số học, đặc biệt là số nguyên tố, chúng ta lại có
thể lần theo được dấu vết của những bài toán cổ xưa để đến được với
những vấn đề mới đang chờ người giải. Hơn nữa, trong thực tế ở trường
phổ thông, những bài toán số học nổi bật và đáng lưu ý là những bài
toán về số nguyên tố luôn có mặt trong các bài thi, các đề thi chọn học
sinh giỏi ở tất cả các cấp học và ở hầu hết các nước trên thế giới. Còn
trong thực tế ngoài xã hội thì số nguyên tố được áp dụng rộng rãi trong
hệ mật mã công nghệ thông tin, làm tăng tính bảo mật trong quân sự,
ngoại giao,...
Chính vì những lý do trên, em đã chọn đề tài "Số nguyên tố và
ứng dụng"
2. Mục đích, nhiệm vụ nghiên cứu
Nghiên cứu về số nguyên tố: định nghĩa, tính chất, lịch sử, nguồn gốc
ra đời và các ứng dụng của nó giúp cho các bạn có cách nhìn bao quát
hơn về số nguyên tố.
3. Đối tượng nghiên cứu
-Số nguyên tố.
1


Khóa luận tốt nghiệp Đại học


Ngô Thị Vân

-Ứng dụng của số nguyên tố trong công nghệ thông tin.
4. Phương pháp nghiên cứu
-Thu thập tài liệu thông tin qua sách giáo trình, sách tham khảo.
-Nghiên cứu lí luận: So sánh, phân tích, tổng hợp,...

2


Chương 1
SỐ NGUYÊN TỐ
1.1

Sơ lược các giai đoạn phát triển của lý thuyết
số nguyên tố

1.1.1

Giai đoạn 1(Trước công nguyên)

Số nguyên tố và các tính chất của nó lần đầu tiên được nghiên cứu
rộng rãi bởi các nhà toán học Hy Lạp cổ đại. Các nhà toán học của
trường học của Pythagoras (500 TCN đến 300 TCN) đã quan tâm đến
các tính chất của số nguyên tố. Họ đã quan tâm đến sự hoàn hảo và
thân thiện của các con số.
Cho đến thời gian xuất hiện cuốn "Nguyên lý" của Euclid (Khoảng
300 TCN), một số kết quả quan trọng về số nguyên tố đã được chứng
minh. Trong sách Nguyên lý IX đã chứng minh rằng có vô hạn số nguyên
tố. Đây là một trong những bằng chứng được biết đến từ rất sớm trong

đó sử dụng phương pháp phản chứng.
Euclid cũng đưa ra một bằng chứng của Định lý cơ bản của số học là
mỗi số nguyên có thể viết thành tích của các số nguyên tố.

3


Khóa luận tốt nghiệp Đại học

Ngô Thị Vân

Euclid cũng cho thấy nếu 2n − 1 là số nguyên tố thì 2n−1 (2n − 1) là
một số hoàn hảo. Nhà toán học Euler (Năm 1947) đã chỉ ra rằng tất cả
các số hoàn hảo đều có dạng trên.
Trong khoảng 200 TCN, Eratosthenes (Hy Lạp) đã nghĩ ra một thuật
toán để tính các số nguyên tố, được gọi là sàng Eratosthenes.
1.1.2

Giai đoạn 2 (Trước thế kỉ 17)

Sau những kết quả đạt được về việc nghiên cứu lý thuyết số nguyên
tố của các nhà toán học Hy Lạp (Trước công nguyên). Thì sau đó một
khoảng cách dài trong lịch sử lý thuyết số nguyên tố không đạt được
thành tựu nào đáng kể, thường gọi là thời kì đen tối.
1.1.3

Giai đoạn 3 (Sau thế kỉ 17)

Những phát triển quan trọng tiếp theo được thực hiện bởi Fermat vào
đầu thế kỷ 17. Ông chứng minh một sự suy đoán của Albert Giard rằng

mỗi số nguyên tố có dạng 4n-1 có thể được viết theo một cách duy nhất
dưới dạng tổng bình phương.
Ông nghĩ ra một phương pháp mới để tìm thừa số của những số lớn
và khai triển số 2027651281=44021.46061.
Ông lần đầu thông báo định lý trong một bức thư đề ngày 18/10/1640
cho bạn ông là Fréniclede Bessy. Như thường lệ Fermat không chứng
minh. Euler lần đầu tiên công bố một chứng minh vào năm 1736 trong
một bài báo, nhưng Lebniz đã có chứng minh với ý tưởng tương tự trong
bản thảo không được công bố vào khoảng trước năm 1683. Điều mà ngày
nay được biết đến như là Định lý Fermat nhỏ. Định lý Fermat nhỏ là
4


Khóa luận tốt nghiệp Đại học

Ngô Thị Vân

một cơ sở cho nhiều kết quả khác trong lý thuyết số và là cơ sở cho
phương pháp kiểm tra lý thuyết số.[11]

1.2
1.2.1

Định nghĩa và tính chất
Định nghĩa

Định nghĩa 1.2.1
Một số tự nhiên lớn hơn 1 và không có ước tự nhiên nào khác ngoài 1
và chính nó được gọi là số nguyên tố.
Kí hiệu tập hợp các số nguyên tố là ℘.

℘={p ∈ N |p là số nguyên tố}.
Định nghĩa 1.2.2
Một số tự nhiên lớn hơn 1 và có nhiều hơn hai ước số (1 và chính nó)
gọi là hợp số.
Nhận xét
+Số 0 và số 1 không phải số nguyên tố cũng không phải là hợp số.
+Trong tập hợp các số nguyên tố thì 2 là số nguyên tố chẵn duy nhất,
các số nguyên tố còn lại đều là các số lẻ.
+Số tự nhiên a là hợp số nếu a>1 và a có một ước là d và 1< d < a.
+Ước số tự nhiên khác 1 và chính nó gọi là ước thực sự.
Từ đó ta có định nghĩa khác về số nguyên tố: số tự nhiên lớn hơn 1 được
gọi là số nguyên tố nếu nó không có ước thực sự.
Ví dụ
2; 3; 5; 7; 11; 13;... là những số nguyên tố.
4; 6; 8; 9; 12;... là những hợp số.

5


Khóa luận tốt nghiệp Đại học

1.2.2

Ngô Thị Vân

Tính chất

Tính chất 1
Ước số tự nhiên nhỏ nhất khác 1 của số tự nhiên a lớn hơn 1 là một số
nguyên tố.

Chứng minh
Giả sử p > 1 là ước nhỏ nhất của a. Ta chứng minh p là số nguyên tố.
Thật vậy, giả sử p không là số nguyên tố thì p là hợp số vì p = 1, nghĩa
là p có một ước thực sự là p1 và 1 < p1 < p.
Từ đó ta có p1 cũng là ước của a và 1 < p1 < p. (mâu thuẫn với giả thiết
p là ước nhỏ nhất lớn hơn 1 của a)
Vậy p là số nguyên tố.
Nhận xét. Tính chất này chỉ ra sự tồn tại của số nguyên tố.
Tính chất 2. Cho số tự nhiên a và số nguyên tố p. Khi đó hoặc (a,p)=1
hoặc p |a.
Chứng minh
Gọi d=(a,p). Suy ra d |p.
Mà p là số nguyên tố nên hoặc d=1 hoặc d = p.
Nếu d=1 thì (a, p) = 1.
Nếu d = p thì p |a.
Tính chất 3
Ước số tự nhiên nhỏ nhất khác 1 của một hợp số a là một số nguyên tố
√
không lớn hơn a.
Chứng minh
Gọi p là ước số tự nhiên nhỏ nhất khác 1 của hợp số a.
Khi đó p là số nguyên tố.
6


Khóa luận tốt nghiệp Đại học

Ngô Thị Vân

Giả sử a = p.p1 , vì a là hợp số nên a = p. Suy ra p1 > 1.

Vậy p1 cũng là một ước lớn hơn 1 của a.
Theo giả thiết p ≤ p1 nên p2 ≤ p.p1 = a.
√
Do đó p ≤ a.
Nhận xét. Tính chất này cho ta cách kiểm tra xem một số tự nhiên a
lớn hơn 1 có phải là số nguyên tố hay không.
"Nếu số tự nhiên a>1 không có một ước nguyên tố nào trong khoảng từ
√
1 đến a thì a là số nguyên tố."
Ví dụ
Số 173 là số nguyên tố.
√
Thật vậy, 132 < 173 < 142 ⇒ 13 < 173 < 14.
√
Các số nguyên tố nhỏ hơn 173 là 2; 3; 5; 7; 11; 13.
Ta thấy 173 không chia hết cho các số nguyên tố này.
Vậy 173 là số nguyên tố.
Tính chất 4
Cho p là số nguyên tố và a1 , a2 , ..., an là các số tự nhiên. Khi đó, nếu
p |a1 .a2 .....an thì tồn tại i ∈ {1, 2, ..., n} để p |ai .
Chứng minh
Nếu p không là ước của ai ,∀i = 1, 2, ..., n thì ta có (ai , p) = 1, ∀i =
1, 2, ..., n..
Suy ra (a1 .a2 ....an , p) = 1 mâu thuẫn với p |a1 .a2 ....an .
Hệ quả
Nếu số nguyên tố p chia hết tích của nhiều số nguyên tố thì nó phải
trùng với một trong các số nguyên tố đó.

7



Khóa luận tốt nghiệp Đại học

1.3

Ngô Thị Vân

Một số định lý cơ bản của số học

1.3.1

Định lý Euclid

Dãy số nguyên tố là dãy số vô hạn.
Chứng minh
Giả sử các số nguyên tố là hữu hạn, bao gồm các số p1 , p2 , ..., pm được
viết theo thứ tự tăng dần. Ta đặt D = p1 .p2 .....pm + 1.
Nếu D là số nguyên tố thì D phải là một trong các số p1 , p2 , ..., pm . Điều
này vô lý vì từ cách xác định D ta có ngay D ≥ pm + 1 . Vậy D là hợp
số.
Gọi p là ước nguyên tố tùy ý của D, suy ra tồn tại pj sao cho p=pj .
Do đó pj |p1 ...pj ...pm + 1. Suy ra pj |1 (vô lý).
Vậy tập số nguyên tố là vô hạn.
1.3.2

Định lý cơ bản của số học

Mọi số tự nhiên a > 1 đều phân tích được thành tích những thừa số
nguyên tố. Sự phân tích đó là duy nhất nếu không kể đến thứ tự các
thừa số.

Chứng minh
a.Sự phân tích được
Giả sử a ∈ N, a > 1. Khi đó a có ít nhất một ước pi nào đó và ta có
a = p1 a1 , trong đó 1 ≤ a1 ≤ a.
Nếu a1 =1 thì a=p1 là sự phân tích của a.
Nếu a1 > 1 thì a1 có ước nguyên tố p2 nào đó và ta có a1 = p2 a2 .
⇒ a = p1 p2 a2 và 1 ≤ a2 ≤ a1 .
8


Khóa luận tốt nghiệp Đại học

Ngô Thị Vân

Nếu a2 =1 thì a = p1 .p2 là sự phân tích của a.
Nếu a2 > 1 thì tiếp tục lặp lại quá trình trên ta được thừa số nguyên tố
p3 ,...
Quá trình này phải kết thúc vì ta có a > a1 > a2 >... nên ắt phải có
an =1, an − 1=pn là một số nguyên tố.
Như vậy, a = p1 p2 ...pn là sự phân tích các thừa số nguyên tố.
b.Tính duy nhất
Giả sử ta có a = p1 p2 ...pn = q1 q2 ...qm là hai dạng phân tích của số tự
nhiên a thành tích các số nguyên tố.
Khi đó, p1 | q1 q2 ...qm nên theo hệ quả của định lý 4 thì p1 trùng với một
qj nào đó (j=1, 2, ...,m).
Do ta không kể đến thứ tự các thừa số nên ta có thể coi p1 =q1 và ta
được p2 ...pn = q2 ...qm .
Lặp lại lý luận trên với p2 , p3 ,... cho tới khi ở một vế không còn thừa số
nguyên tố nào nữa, ta được p2 = q2 , p3 = q3 ... vì không thể xảy ra các
đẳng thức qn+ 1 .qn+2 .....qm = 1 hoặc là pm+1 .pm+2 .....pn = 1 .

Nên ta có m = n và pi =qi , ∀i= 1, 2,..., n.
Vậy ta có điều phải chứng minh.
1.3.3

Dạng phân tích tiêu chuẩn

Trong sự phân tích a > 1 thành một tích những thừa số nguyên tố có
thể xảy ra nhiều thừa số lặp lại. Gọi p1 , ...., pk là các ước nguyên tố đôi
một khác nhau của a và αj (1 ≤ j ≤ k) là số các nhân tử cùng là pi
trong sự phân tích thành thừa số nguyên tố, ta sẽ có
a = p1 α1 pα2 2 .....pk αk
9


Khóa luận tốt nghiệp Đại học

Ngô Thị Vân

Sự phân tích như trên được gọi là sự phân tích tiêu chuẩn của a.
Nếu thừa số nguyên tố pm không có mặt trong sự phân tích ta có thể
viết
a = p1 α1 pα2 2 .....pk αk pm 0
Từ đó, với mọi số nguyên a = 0 đều có dạng phân tích tiêu chuẩn
a = ±p1 α1 pα2 2 .....pk αk
Ví dụ
720 = 24 .32 .51
1320 = 23 .31 .51 .70 .111
1.3.4

Một số ứng dụng của định lý cơ bản


a.Tiêu chuẩn chia hết
Định lý.Cho a là một số tự nhiên với dạng phân tích tiêu chuẩn
a = p1 α1 pα2 2 .....pk αk . Khi đó d là ước của a khi và chỉ khi
d = p1 β1 pβ2 2 .....pk βk với 0 ≤ βi ≤ αi , i=1, 2,..., k.
Chứng minh
⇒]
Giả sử d |a, nghĩa là có số nguyên tố q sao cho a = d.q.
Nếu d = 1 thì d = p1 0 p02 ...pk 0 .
Giả sử d > 1, theo định lý cơ bản, đẳng thức a = d.q chứng tỏ mọi ước
nguyên tố của d là ước nguyên tố của a và số mũ của ước nguyên tố
ấy trong dạng phân tích tiêu chuẩn của d không lớn hơn số mũ của nó
trong dạng phân tích tiêu chuẩn của a.
Do đó, d = p1 β1 pβ2 2 ...pk βk với 0 ≤ βi ≤ αi , i = 1, k .
⇐]
10


Khóa luận tốt nghiệp Đại học

Ngô Thị Vân

Giả sử d = p1 β1 pβ2 2 ...pk βk , 0 ≤ βi ≤ αi , i = 1, k.
Khi đó αi − βi ≥ 0, i = 1, k nên ∃q = p1 α1 −β1 .p2 α2 −β2 .....pk αk −βk là một số
tự nhiên và a = d.q nghĩa là d |a.
Hệ quả
Cho a và b là hai số tự nhiên khác 0 nguyên tố cùng nhau. Khi đó số tự
nhiên d là ước của tích a.b khi và chỉ khi d = r.s, trong đó r là ước của
a, s là ước của b với r, s nguyên tố cùng nhau.
b.Ước chung lớn nhất - Bội chung nhỏ nhất

Giả sử p1 , p2 , ..., pn là tất cả các ước nguyên tố phân biệt của ít nhất một
trong hai số a và b, ta có thể viết
a=p1 α1 p2 α2 , ..., pn αn , αi ≥ 0, i = 1, n.
b = p1 β1 p2 β2 , ..., pn βn , βi ≥ 0, i = 1, n.
Khi đó ta có
a) ƯCLN (a, b)=p1 x1 p2 x2 ...pn xn , trong đó xi = min(αi , βi ), i = 1, n.
b) BCNN (a, b)=p1 y1 p2 y2 ...pn yn , trong đó yi = max(αi , βi ), i = 1, n.

Thật vậy
a) Từ giả thiết với i = 1, n ta có xi ≤ αi , xi ≤ βi nên p1 x1 p2 x2 .....pn xn là
ước của a và ước của b.
Mặt khác, d là ước chung của a và b thì d = p1 z1 p2 z2 .....pn zn , trong đó
0 ≤ zi ≤ αi , 0 ≤ zi ≤ βi , i = 1, n.
Nghĩa là zi ≤ xi cho nên d| p1 x1 p2 x2 .....pn xn .
Vậy ƯCLN (a, b) = p1 x1 p2 x2 .....pn xn .
b)Từ giả thiết với i = 1, n ta có αi ≤ yi , βi ≤ yi nên p1 y1 .p2 y2 .....pn yn là
bội chung của a và b.

11


Khóa luận tốt nghiệp Đại học

Ngô Thị Vân

Hơn nữa, giả sử m là một bội chung của a và b thì m phải có dạng m=
p1 t1 .p2 t2 .....pn tn , ở đó αi ≤ ti , βi ≤ ti (i = 1, n), nghĩa là ti ≥ yi cho nên
m là bội của p1 y1 .p2 y2 .....pn yn .
Vậy BCNN(a, b) = p1 y1 p2 y2 .....pn yn .
Ví dụ

2100 = 22 .3.52 .7.
3240 = 24 .33 .5.
3675 = 3.52 .72 .
Ta có
ƯCLN(2100, 3240, 3675) = 22 .3.5.7 = 420.
BCNN(2100, 3240, 3675) = 24 .33 .52 .72 = 529200.
c.Số các ước và tổng các ước tự nhiên của một số tự nhiên
Với số tự nhiên n ≥ 1, ta kí hiệu
+τ (n) là số các ước tự nhiên của n.
+σ(n) là tổng số các ước tự nhiên của n.
a) Công thức tính τ (n)
+Với n = 1 ta có τ (1)=1.
+ Với n > 1 và giả sử n có dạng phân tích tiêu chuẩn n = p1 α1 .p2 α2 .....pk αk
Ta có τ (n) = (α1 + 1)(α2 + 1)...(αk + 1).
b) Công thức tính σ(x)
+ Với n = 1 ta có σ(1)=1.
+ Với n > 1 và giả sử n có dạng phân tích tiêu chuẩn n = p1 α1 .p2 α2 .....pk αk
Ta có σ(n) =

pk αk +1 −1
p1 α1 +1 −1 p2 α2 +1 −1
p1 −1 . p2 −1 ..... pk −1 .

Ví dụ

12


Khóa luận tốt nghiệp Đại học


Ngô Thị Vân

n = 720 = 24 .32 .5 .
Ta có
τ (720) = 5.3.2 = 30 .
σ(720) =

25 −1 33 −1 52 −1
2−1 . 3−1 . 5−1

= 2418.

d.Số hoàn chỉnh
Định nghĩa
Số tự nhiên n = 0 được gọi là số hoàn chỉnh nếu σ(n)=2n.
Ví dụ
n = 6 là số hoàn chỉnh vì σ(6) = 1+2+3+6=2.6
Định lý
Điều kiện cần và đủ để một số chẵn là số hoàn chỉnh là nó có dạng
n = 2k−1 (2k − 1), trong đó k ≥ 2 và p=2k - 1 là số nguyên tố.
Chứng minh
⇒]
Giả sử n = 2k−1 (2k − 1) , k ≥ 2 và p = 2k − 1 là số nguyên tố.
Khi đó, (p, 2) = 1 nên n=2k−1 .p là dạng phân tích tiêu chuẩn của n.
Do đó σ(n) = σ(2k−1 )σ(p) = (2k − 1)(1 + p) = (2k − 1).2k
Hay σ(n) = 2.2k−1 .(2k − 1) = 2n.
Vậy n là số hoàn chỉnh chẵn.
⇐]
Giả sử n là số hoàn chỉnh chẵn.
Gọi lũy thừa của 2 trong dạng phân tích tiêu chuẩn của n là 2k − 1.

Ta có k ≥ 2 và n = 2k−1 .b, trong đó b là số lẻ.
Khi đó ƯCLN(2k−1 ,b)=1 nên σ(n) = σ(2k−1 )σ(b)
Theo giả thiết n là số hoàn chỉnh, nghĩa là σ(n) = 2n = 2k .b

13


Khóa luận tốt nghiệp Đại học

Ngô Thị Vân

⇒ (2k − 1)σ(b) = 2k .b
Chứng tỏ 2k − 1 2k .b nhưng do ƯCLN(2k − 1, 2k )=1
Suy ra 2k − 1 |b, tồn tại c ∈ N (c < b) sao cho b = (2k − 1).c
Nếu σ(b) = 2k .c = (2k − 1).c + c thì σ(b) =b + c.
Do đó b là số nguyên tố và c = 1.
Thật vậy, nếu b không là số nguyên tố và c = 1 thì do b > 1 phải có ít
nhất là ba ước tự nhiên là b, c và một ước khác nữa.
Khi đó σ(b)>b + c ( vô lý ) .
⇒ b là số nguyên tố và c = 1.
Do đó n = 2k−1 (2k − 1) trong đó k ≥ 2 và 2k -1 là một số nguyên tố.
Nhận xét
i) Nếu b=2k -1 là số nguyên tố thì k cũng phải là số nguyên tố. Các số
nguyên tố dạng 2k -1 được gọi là số nguyên tố Mersenne. Như vậy là mỗi
số nguyên tố Mersenne cho ta một số hoàn chỉnh chẵn và ngược lại.
ii) Người ta chưa tìm được số hoàn chỉnh lẻ nào và bài toán có hay không
một số hoàn chỉnh lẻ chưa được giải quyết.

1.4
1.4.1


Một số định lý nổi tiếng về số nguyên tố
Định lý Wilson

Định lý
Cho p là số tự nhiên lớn hơn 1, p là số nguyên tố khi và chỉ khi (p−1)!+1
chia hết cho p.
Chứng minh
⇒]

14


Khóa luận tốt nghiệp Đại học

Ngô Thị Vân

.
Giả sử p là số nguyên tố. Ta chứng minh (p − 1)! + 1 .. p
.
+ Nếu p = 2 thì (p − 1)! + 1 = 2 .. 2
.
+ Nếu p = 3 thì (p − 1)! + 1 = 3 .. 3
Do đó định lý đúng với p = 2 và p = 3.
+ Nếu p > 3 ta xét tập hợp A={2, 3, ..., p − 2}
Với mỗi (k ∈ A) (∃!k : 1 ≤ k ≤ p − 1)sao cho k.k ≡ 1 (mod p). Ta
chứng minh rằng k ∈ A.
Vì 1 ≤ k ≤ p − 1 và A={2, 3, ..., p − 2} nên để chứng minh k ∈ A ta
chỉ cần chứng minh k = 1 và k = p − 1.
Thật vậy,

+ Nếu k =1 thì từ k.k ≡ 1 (mod p) ⇒ k ≡ 1 (mod p) ⇒ k ∈
/ A.
Do đó k ∈ A ⇒ k ≡ 1 (mod p). (vô lý)
Vậy k = 1
+ Nếu k = p − 1 thì k(p − 1) ≡ 1(modp) ⇒ k ≡ −1 (mod p). Điều này
cũng vô lý.
Vậy k = p − 1.
Vậy ta chứng minh được k ∈ A.
Tiếp theo ta chứng minh k = k .
Thật vậy, nếu k = k thì từ k.k ≡ 1 (mod p) ta có k 2 ≡ 1 (mod p)
(k-1)(k+1)≡ 0 (mod p).
⇒ k = 1 hoặc k = p − 1. Điều này mâu thuẫn vì k ∈ {2, 3, ..., p − 2}.
Các phần tử của A = {2, 3, ..., p − 2} được ghép thành
với k.k ≡ 1(mod p). ( Dop lẻ nên có

p−3
2

cặp chẵn)

Từ đó suy ra 2.3.4....(p − 3)(p − 2) ≡ 1 (mod p)
⇒ (p-1)!≡ (p − 1) (mod p)

15

p−3
2

cặp (k, k )



Khóa luận tốt nghiệp Đại học

Ngô Thị Vân

.
⇒ [(p − 1)! + 1] ≡ p (mod p) hay [(p − 1)! + 1] ..p
.
Vậy [(p − 1)! + 1] .. p.
⇐]
.
Giả sử p là số nguyên dương lớn hơn 1 và thỏa mãn [(p − 1)! + 1] .. p. Ta
chứng minh p là số nguyên tố.
Giả sử p không là số nguyên tố, tức p có thể biểu diễn được dưới dạng
p = a.b với 1 < a ≤ b < p.
.
Do a nguyên nên 1 < a ≤ p − 1 ⇒ (p − 1)! .. a
.
Theo giả thiết [(p − 1)! + 1] .. p = a.b .
.
Suy ra [(p − 1)! + 1] .. a (mâu thuẫn) .
Do đó điều giả sử là sai.
Vậy p là số nguyên tố.
1.4.2

Định lý Fermat nhỏ

Định lý
.
Nếu p là một số nguyên tố thì với số nguyên a bất kỳ ta đều có ap − a .. p.

Nghĩa là ap ≡ a (mod p) .
Phát biểu khác của định lý
.
Nếu p là số nguyên tố và a là số nguyên sao cho (a, p) = 1 thì ap−1 −1 .. p.
Nghĩa là, ap−1 − 1 ≡ 1 (mod p) .
Nhận xét
Định lý Fermat nhỏ là cơ sở để kiểm tra tính nguyên tố theo xác suất
trong kiểm tra Fermat.
Chứng minh
Cách 1
16


Khóa luận tốt nghiệp Đại học

Ngô Thị Vân

Nhận xét.
Do (a, p) = 1 nên a không chia hết cho p. Vì thế các số 2a, 3a, ..., (p−1)
cũng không chia hết cho p.
Giả sử các số 2a, 3a, ..., (p−1) chia cho p được các số dư là r1 , r2 , ..., rp−1 .
Ta chứng minh rằng ri = rj ∀i = j(1 ≤ i, j ≤ p − 1)
Thật vậy, nếu trái lại thì tồn tại i = j(1 ≤ i, j ≤ p − 1) mà ri = rj .
Do


 ja ≡ r (modp)
j
 ia ≡ r (modp)
i


.
Mà ri = rj ⇒ ia ≡ ja (mod p) ⇒ a(i − j) .. p .
Do 0 < |i − j| < p ⇒ (i − j, p) = 1 .
.
⇒ a .. p (vô lý).
Vậy nhận xét được chứng minh.
Vì vậy r1 r2 ...rp−1 = (p − 1)!
⇒ 2a.3a...(p − 1)a ≡ r1 r2 ...rp−1 (mod p).
Suy ra ap−1 (p − 1)! ≡ (p − 1)! (mod p) .
⇒ ap−1 ≡ 1(mod p).
Cách 2
.
Ta cần chứng minh ap − a .. p, ∀a ∈ Z∗ ( trường hợp còn lại chứng minh
tương
 tự)
a=0
.
Khi 
⇒ ap − a.. p
a=1
(1) Vậy định lý đúng trong trường hợp a = 0va = 1.
.
Giả sử mệnh đề đúng với a = k. Ta có (k p − k).. p
Xét khi a = k + 1. Theo Nhị thức Newton ta có
17


Khóa luận tốt nghiệp Đại học


Ngô Thị Vân

(k + 1)p − (k + 1) = k p + p.k p−1 + Cp2 .k p−2 + ... + p.k + 1 − k − 1
= ((k p − k) + p.k p−1 + Cp2 .k p−2 + ... + p.k) (2)
.
Từ (1) ta có (k p − k).. p.
..
Mặt khác Cpn = p(p−1).....(p−n−1)
. p ( ∀n ≤ p ).
1.2.3.....n
.
Suy ra pk p−1 + Cp2 k p−2 + ... + p.k .. p.
.
Từ (2) suy ra (k + 1)p − (k + 1) .. p .
Vậy định lý đúng với a = k + 1.
Theo nguyên lý quy nạp ta có điều phải chứng minh.
Tổng quát hóa
Một dạng tổng quát của định lý Fermat là :" Nếu p là số nguyên tố và
m, n là các số nguyên dương thỏa mãn m ≡ n (mod p − 1) thì ∀a ∈ Z
sao cho am ≡ an (mod p).
Định lý Fermat còn được tổng quát bởi định lý Euler: Với môdun n bất
kì và số nguyên a bất kì nguyên tố cùng nhau với n ta có aϕ(n) ≡ 1 (mod
n). Trong đó ϕ(n) là hàm Euler.
Nếu n = p là số nguyên tố thì ϕ(n)=p − 1.
1.4.3

Định lý Korelt

Như ta đã biết, nếu p là số nguyên tố thì theo định lý Fermat nhỏ ta có
p là ước của ap − a, ∀a ∈ Z. Câu hỏi được đặt ra là:"nếu p là số tự nhiên

lẻ và p là ước của ap − a, ∀a ∈ Z thì p có là số nguyên tố hay không?
Nếu điều này đúng thì ta có một tiêu chuẩn để kiểm tra một số tự nhiên
có phải là số nguyên tố hay không?". Năm 1899, nhà toán học Korelt
chứng minh được định lý sau.
" Số nguyên tố n > 1 là ước của ap − 1, ∀a ∈ Z∗ khi và chỉ khi n không
18