Một số định lý cơ bản của số học
Trường đại học sư phạm hà nội 2 Khoa Toán
=====o0o=====

NGÔ THỊ MINH DIỆU

Một số định lý cơ bản
của số học
Khoá Luận tốt nghiệp đại học
Chuyên ngành: Đại số

Hà Nội – 2008

Ngô Thị Minh Diệu

1

K30G – Sư phạm Toán



Trường đại học sư phạm hà nội 2
Khoa Toán
=====o0o=====

NGÔ THỊ MINH DIỆU

Một số định lý cơ bản
của số học
Khoá Luận tốt nghiệp đại
học

Chuyên ngành: Đại số

Người hướng dẫn khoa học
Th.s Nguyễn Huy Hưng

Hà Nội - 2008


Lời cảm ơn
Bản khoá luận tốt nghiệp này là bước đầu tiên để em làm quen với việc
nghiên cứu khoa học. Trước sự bỡ ngỡ và gặp nhiều khó khăn khi mới làm
quen với công tác nghiên cứu khoa học em đã nhận được sự giúp đỡ, động
viên của các thầy cô giáo và các bạn sinh viên trong khoa. Em xin chân thành
cảm ơn sự giúp đỡ quý báu của các thầy cô trong tổ Đại số, các thầy cô trong
khoa Toán, các thầy cô trong trường ĐHSP Hà Nội 2 và các bạn sinh viên.
Đặc biệt em xin gửi lời cảm ơn chân thành sâu sắc tới Thạc sĩ Nguyễn Huy
Hưng người đã giúp đỡ, hướng dẫn tận tình để em hoàn thành khoá luận này.
Em cũng xin chân thành cảm ơn ban chủ nhiệm khoa Toán đã tạo điều kiện
cho em có cơ hội để tập dượt với việc nghiên cứu khoa học.
Hà Nội, tháng 5 năm 2008
Sinh viên
Ngô Thị Minh Diệu


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

Lời cam đoan
Khoá luận của em được hoàn thành dưới sự hướng dẫn của Thạc sỹ
Nguyễn Huy Hưng cùng với sự cố gắng của bản thân. Trong quá trình nghiên
cứu và thực hiện khoá luận em có tham khảo tài liệu của một số tác giả có nêu

trong mục tài liệu tham khảo. Em xin cam đoan những kết quả trong khoá
luận là kết quả nghiên cứu của bản thân, không trùng với kết quả của các tác
giả khác. Nếu sai em xin hoàn toàn chịu trách nhiệm.
Hà Nội, tháng 5 năm 2008
Sinh viên
Ngô Thị Minh Diệu


Mục lục

Trang

Lời cảm ơn…………………………………………………………..

1

Lời cam đoan………………………………………………………..

2

Mục lục……………………………………………………………...

3

Lời mở đầu…………………………………………………………..

4

Chương 1. Một số định lý cơ bản về số nguyên tố
1.1 Định nghĩa số nguyên tố……………………………………


6

1.2 Một số định lý cơ bản về số nguyên tố……………………

6

1.3 Một số ứng dụng…………………………………………….

10

1.4 Một số bài toán về số nguyên tố……………………………

11

Chương 2. Một số định lý cơ bản về đồng dư
2.1 Quan hệ đồng dư…………………………………………....

21

2.2 Định lý Euler. Định lý Wilson……...………………………

25

2.3 Phương trình đồng dư………………………………………

27

2.4 Định lý Thặng dư Trung Hoa……………………………….


31

2.5 Thặng dư toàn phương. Luật thuận nghịch bình phương…

34

2.6 Một số bài tập áp dụng……………………………………...

40

Kết luận…………………………………………………………......

49

Tài liệu tham khảo………………………………………………....

50


Lời mở đầu
Toỏn học là mụn khoa học cơ bản, là chỡa khoỏ mở ra nhiều mụn khoa
học khỏc. Từ thời xa xưa, do yờu cầu của thực tế đời sống, sản xuất, sinh
hoạt, đầu thế kỷ thứ VII, người Ấn Độ đó biết dựng cỏc ký hiệu đặc biệt để
viết cỏc chữ số 0, 1, 2…, 9 ( Ngày nay gọi là cỏc chữ số Ả Rập ). Từ thế kỷ II
trước cụng nguyờn, người La Mó đó dựng hỡnh ảnh ngún tay, bàn tay để ký
hiệu chỉ cỏc chữ số 1, 5… Rồi đến sự ra đời của chiếc bàn tớnh đầu tiờn, đến
nay là chiếc mỏy tớnh với nhiều chức năng tinh vi, hiện đại.
Cỏc kiến thức về số học mà điểm xuất phỏt đầu tiờn là số tự nhiờn là
chỡa khoỏ để mở cửa vào thế giới cỏc con số.
Những kiến thức nền múng và quan trọng về Toỏn học núi chung và số

học núi riờng sẽ mang đến cho chỳng ta nhiều điều mới mẻ và thỳ vị.
Ngay từ cấp học Tiểu học, học sinh đó được làm quen và cú kỹ năng
thành thạo khi giải cỏc bài toỏn liờn quan đến cỏc phộp tớnh cộng, trừ, nhõn,
chia số tự nhiờn. Khi học sinh học lờn cấp học THCS, THPT bờn cạnh việc
được ụn tập, hệ thống hoỏ cỏc nội dung về số tự nhiờn đó học, cỏc em cũn
tỡm hiểu thờm nhiều nội dung mới: phộp nõng lờn luỹ thừa, số nguyờn tố và
hợp số, ước chung và bội chung, quan hệ đồng dư…
Trong chương trỡnh toỏn phổ thụng, lý thuyết số được xem là nội dung
khú với những bài toỏn phức tạp với nhiều cỏch giải thỳ vị. Trong cỏc kỳ thi
học sinh năng khiếu, học sinh giỏi cỏc cấp, nội dung số học: Số nguyờn tố,
quan hệ đồng dư… chiếm tỷ lệ khỏ cao trong cỏc đề thi. Vỡ vậy, để giỳp cỏc
em học sinh cú cỏch nhỡn tổng quỏt, toàn diện về hệ thống số, đặc biệt là cỏc
kiến thức, cỏc định lý cơ bản để từ đó cú thể giải được những bài toỏn về số
nguyờn tố, bài toỏn về quan hệ đồng dư… nờn em chọn nội dung: “ Một số
định lý cơ bản của số học” làm luận văn nghiờn cứu.
Khoá luận của em gồm hai chương :


Chương 1 : Một số định lý cơ bản về số nguyên tố.
Chương 2 : Một số định lý cơ bản về đồng dư.
Mặc dù đã có nhiều cố gắng song không tránh khỏi những thiếu sót, vì
vậy em rất mong nhận được ý kiến đóng góp của các thầy cô giáo và các bạn
sinh viên cho bài khoá luận của em. Em xin chân thành cảm ơn!
Hà Nội, tháng 5 năm 2008
Sinh viên:
Ngô Thị Minh Diệu



Chương 1. Một số định lý cơ bản về

số nguyên tố
1.1 Định nghĩa số nguyên tố :
* Định nghĩa:
- 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 P là tập hợp các số nguyên tố. Khi
đó : P = { p ∈   p nguyên
tố }.
- Số tự nhiên lớn hơn 1 mà không là số nguyên tố gọi là hợp số.
- Ước của số tự nhiên khác 1 và khác chính nó được gọi là ước thực sự.
Khi đó định nghĩa số nguyên tố có thể được phát biểu lại như sau: 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ự.
* Nhận xét :
- Số 1 và số 0 đều không phải là số nguyên tố mà cũng không phải là hợp số
( số 1 chỉ có một ước số, số 0 có vô số ước số ).
- Mỗi số tự nhiên

n
có một và chỉ một trong ba khả năng : n = 1;
∈
*

n là số nguyên tố, n là hợp số.
1.2. Một số định lý cơ bản về số nguyên tố:
Bổ đề 1.2.1 :
Mọi số nguyên lớn hơn 1 đều chia hết cho ít nhất một số nguyên tố .
Chứng minh:
Ta chứng minh bằng quy nạp.
+ Với n = 2, do 2 là số nguyên tố nên bổ đề đúng.



+ Xét n > 2 và giả sử bổ đề đúng với mọi số nguyên lớn hơn 1 và nhỏ
hơn n. Ta sẽ chứng minh bổ đề đúng với n.
Nếu n là số nguyên tố thì n  n và bổ đề đúng.
Nếu n là hợp số thì n có ước dương a với a ≠ 1, a ≠ n. Giả sử n = a.b.


Nếu a > n thì từ b ≥ 1 ta có n = a.b > n.1 = n, mâu thuẫn. Vậy 1 < a < n.
Theo giả thiết quy nạp, a có ước nguyên tố p. Từ p | a, a | n suy ra p | n.
Vậy bổ đề đúng với mọi n > 1.
Định lý 1.2.2 ( Định lý Euclid )
Tồn tại vô hạn các số nguyên tố.
Chứng minh:
Giả sử chỉ có hữu hạn các số nguyên tố là p1, p2,…, pn.
Khi đó đặt N = p1.p2…pn + 1, thế thì theo bổ đề (1.2.1), N chia hết cho
một số nguyên tố p nào đó ( vì N > 1 ). Số nguyên tố p này bắt buộc phải là
một trong các số pi, do chỉ có n số nguyên tố p1, p2,…, pn mà thôi. Tuy nhiên,
theo định nghĩa của N, N không thể chia hết cho số pi nào cả. Mâu thuẫn này
cho ta điều phải chứng minh.
Định lý 1.2.3 :
Cho số tự nhiên a và một số nguyên tố p. Khi đó hoặc p | a hoặc
(a,p)=1.
Chứng minh :
Gọi d = (a,p) ⇒ d | p với p là số nguyên tố. Từ đó hoặc d = 1 hoặc d
= p.
+ Nếu d = 1 thì (a, p) = 1.
+ Nếu d = p thì p | a.
Định lý 1.2.4 : ( Bổ đề cơ bản các số nguyên tố - Bổ đề Euclid) :
Nếu một số nguyên tố p chia hết tích ab của hai số nguyên a và b thì p
phải chia hết ít nhất một trong hai số a và b.

Chứng minh :
Giả sử p | ab nhưng p không chia hết a và không chia hết b. Khi đó theo
định lý (1.2.3) ta có (a,p) =1 và (b,p) = 1, từ đó ta có (ab,p) =1 ( trái giả thiết p
| ab). Từ đó, ta có điều phải chứng minh.



Nhận xét : Bằng quy nạp, chúng ta có thể mở rộng kết quả này cho nhiều số
và khi đó định lý (1.2.4) được mở rộng như sau:
Nếu một số nguyên tố p chia hết tích a1.a2 … an thì p chia hết ai, với i
nào đó thuộc { 1, 2,…, n }.
Ví dụ : Giả sử p là số nguyên tố.
3

a. Chứng minh rằng nếu p | a thì p | a.
2

2

b. Chứng minh rằng nếu p | b và p | ( a + b ) thì p | a.
Giải:
3

a. Giả sử p | a = a.a.a. Khi đó theo bổ đề Euclid ta có p | a hay p | a hay p |
a, tức là p | a.
2

2

b. Giả sử p | b và p | ( a + b ). Khi đó ta có :

2

2

p | [( a + b ) - b.b] = a.a
Từ đó và từ bổ đề Euclid ta có p | a.
Hệ quả 1.2.5:
Nếu một 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ố đó.
Bổ đề 1.2.6 :
Mọi hợp số có ước thực sự nhỏ hơn hoặc bằng căn bậc hai của nó.
Chứng minh:
Cho n là hợp số. Khi đó ta có thể viết n = a.b với 1 < a, b < n.
Nếu đồng thời a, b >

n thì n =

n

n < ab = n < mâu thuẫn >.

.
Vậy có ít nhất một trong hai số a, b phải nhỏ hơn hoặc bằng n .
Từ bổ đề này ta có nhận xét sau :
Mỗi hợp số phải có ước nguyên tố nhỏ hơn hoặc bằng căn bậc hai của
nó


Dựa vào nhận xét trên ta có thể kiểm tra xem một số nguyên dương cho
trước bất kỳ là số nguyên tố hay không?



Ví dụ : Để xác định a = 89 có là số nguyên tố không ta chỉ cần xem nó có
ước nguyên tố bé hơn hoặc bằng

89 không? Ta có

89 = 9,43 và các số

nguyên tố nhỏ hơn hoặc bằng 9,43 là 2; 3; 5; 7 đều không là ước của 89.
Vậy 89 là số nguyên tố.
Cho một số tự nhiên a > 1 bất kỳ. Vấn đề đặt ra là liệu có thể biểu thị a
dưới dạng tích của các thừa số nguyên tố được hay không và có bao nhiêu
cách biểu thị như vậy? Vấn đề đó được giải quyết trong định lý sau:
Định lý 1.2.7 < Đị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ố và sự phân tích đó là duy nhất nếu không kể đến thứ tự của các thừa số.
Chứng minh:
a. Sự phân tích được :
Giả sử a ∈  , a > 1. Khi đó theo bổ đề (1.2.1) a có ít nhất một
ước nguyên tố p1 nào đó và ta có a = p1 . a1, a1∈ 
Nếu a1 = 1 thì a = p1 là cách phân tích tầm thường của a.
Nếu a1 > 1 theo lý luận trên, a1 có ước nguyên tố p2 nào đó và ta có :
a1 = p2 . a2, a2∈  nên a = p1.p2.a2
Nếu a2 = 1 thì a = p1. p2 là phân tích của a .
Nếu a2 > 1 lại tiếp tục lý luận như trên, có số nguyên tố p3 ,…
Quá trình này phải kết thúc, nghĩa là ắt có n sao cho an = 1, an-1 = pn là
một số nguyên tố, bởi vì ta có a, a1, a2,… là một dãy những số tự nhiên mà
a > a1 > a2 >… Như vậy, ta được a = p1 .p2… pn là sự phân tích của a thành
tích những thừa số nguyên tố .

b. Sự duy nhất:
Giả sử ta có a = p1.p2…pn = q1.q2…qm là hai dạng phân tích của a thành
tích của những thừa số nguyên tố. Đẳng thức trên chứng tỏ p1 là ước của
q1.q2…qm nên p1 phải trùng với một qj nào đó ( 1 ≤ j ≤ m ). Vì không kể đến

Ngô Thị Minh Diệu

11

K30G – Sư phạm Toán


thứ tự của các thừa số nên có thể coi p1 = q1 từ đó ta được p2.p3…pn =
q2.q3..qm. Ta lấy p2 và lặp lại cho đến khi ở một vế không còn thừa số nguyên
tố nào nữa. Nhưng lúc đó, ở vế còn lại cũng không còn thừa số nguyên tố nào
vì nếu ngược lại sẽ xảy ra hoặc 1 = qn+1.qn+2…qm hoặc pm+1.pm+2…pn = 1 là
không thể
được. Vì vậy phải có m = n và pi = qi , i = 1, 2,…, n nghĩa là phân tích của a là
duy nhất.
Chú ý :
- Nếu trong sự phân tích ra thừa số nguyên tố của một số tự nhiên a, một
thừa số nguyên tố pi được lặp lại αi lần thì ta viết :
α

α

α2

1
a = αp

.p
n
...p

1

2

i = 1, 2,…, n

>1

n

i

- Nếu thừa số nguyên tố pm không có mặt trong sự phân tích thì ta có
α1
α2
thể αviết
a
=
p
.
p
0
từ đó suy ra mọi số tự nhiên a đều có sự phân
...p n p
1


2

n

m

α1

α2

2

k

tíchαkduy nhất a = p . p
...p
1

pk ∈ P, αi ≥ 0 gọi là dạng phân tích tiêu
chuẩn

của số tự nhiên a.
- Từ đó với mọi số nguyên n ≠ 0 đều có dạng phân tích tiêu chuẩn :
n=±

p

α1

1


α

. p 2 ...p
2

αk

k

1.3. Một số ứng dụng :
1.3.1 số :
+) Cho a =

α

p 1 α. np
...p
1

α =1,2,..., n

α2

2

n

i


d | a d = pβ1 .p β2
β
...p n
1

2

với 0 ≤ õi ≤ αi i = 1, 2,.., n
n

+) Muốn xác định tất cả các ước của a ta cho các õi lần lượt chạy từ 0 đến

Ngô Thị Minh Diệu

17

K30G – Sư phạm Toán


.

αi .
Vậy số các ước của a là (α1 + 1) (α2 + 1 )… (αn + 1 )
+) Cho ( a, b) =1. Khi đó :
d | ab d = xy với x | a, y | b và (x , y) = 1.

Ngô Thị Minh Diệu

18


K30G – Sư phạm Toán


1.3.2 ớc chung lớn nhất ( ƯCLN ):
- Một số nguyên c được gọi là ước chung của các số nguyên a1, a2,…, an khi c
là ước của từng số đó.
- Một ước chung d của các số nguyên a1, a2 ,.., an được gọi là ước chung lớn
nhất nếu mọi ước chung của chúng đều là ước của d.
- Giả sử cho các số tự nhiên lớn hơn 1 là a1, a2 ,.., an. Gọi p1, p2 ,.., pn là các
ước nguyên tố phân biệt của các số đó.
Giả sử các số ai có dạng :
α.p
αi
i1

ai =

p1

2

...p
αik

2

αij ≥ 0 , j = 1, 2,…, k ; i = 1, 2,…, n.

k


thế thì số d = p .p ...p với ỡj = min ( α1j, α2j,…, αnj ) là số nhỏ
nhất trong
µ1

1

µ2

2

µk

k

các số α1j, α2j,…, αnj sẽ là ước chung lớn nhất của a1, a2 ,.., an.
Thật vậy, d | ai i = 1, 2,.., n và mọi ước chung của a1, a2,.., an đều là ước của
d.
1.3.3 Bội chung nhỏ nhất ( BCNN ):
- Một số nguyên m được gọi là bội chung của các số nguyên a1, a2,.., an khi m
là bội của mỗi số đó.
- Một bội chung m của các số nguyên a1, a2,.., an được gọi là BCNN nếu
mọi bội chung của chúng đều là bội của m.
- Cũng bằng các ký hiệu ở trên ta có :
Số m
=

γ

p 1 .p
γ

...p k
1

γ

2

2

k

với γj = max ( α1j , α2j ,…, αnj ) là số lớn nhất
trong

các số α1j , α2j ,…, αnj là BCNN của a1, a2,.., an. Thật vậy, m là bội
chung của a1, a2,.., an và mọi bội chung của a1, a2,.., an đều là bội của m.
Ví dụ :
Tìm ƯCLN, BCNN của 720, 225, 1000


Ta có 720
225

4

2

=2 .3 .5
=


2

2

3 .5


3

3

1000 = 2 .

5

0

0

Vậy ( 720, 225, 1000 ) = 2 . 3 . 5 = 5
4

2

3

[ 720, 225, 1000 ] = 2 . 3 . 5 = 18000.
1.4.Một số bài toán về số nguyên tố:
1.4.1 Dạng 1:
Dùng phương pháp phân tích để:

i. Tìm điều kiện để một số là số nguyên tố.
ii. Chứng minh một số là hợp số.
Bài
1:

Tìm tất cả các số tự nhiên n để:
4

a, n + 4 là số nguyên tố.
1991

1990

b, n

+n

+ 1 là số nguyên tố.

Giải:
a.

4

4

2

2


n + 4 = n + 4n + 4 - 4n
2

2

= ( n + 2 ) - (2n)

2

2

2

= ( n + 2 - 2n ) ( n + 2 + 2n )
2

4

Vì n + 2 + 2n > 1 nên để n + 4 là số nguyên tố thì
2

n + 2 - 2n = 1
2

⇔

n - 2n + 1 = 0

⇔
4


n = 1 Với n = 1 thì n + 4 = 5 là số
nguyên tố.
4

Kết luận: n = 1 thì n + 4 là số nguyên tố.
b.

1991

n

1990

+n
2

1989

=n(n

( Vì n

Ngô Thị Minh Diệu

1991

+1=n

2


1989

- 1 ) + n( n

1989

1990

-n +n

3 663

- 1 = (n )

21

2

-n+n+n+1
2

2

-1)+n +n+1 n +n+1
3

2

−1n −1n + n +1 )


K30G – Sư phạm Toán


1991

Vậy để n

1990

+n

1991

+ 1 là số nguyên tố thì n

1990

+n

2

+1=n+n+1

⇔ n = 1.

Ngô Thị Minh Diệu

22


K30G – Sư phạm Toán


1991

1990

Với n = 1 thì n

+n

+ 1 = 3 là số nguyên tố.

Bài
2:
n

Chứng minh rằng nếu 1 + 2 +

k
n
) là số nguyên tố thì n = 3
∈
*

n

4 ( với k ∈  .
Giải :
k


Đặt n = 3 . m với ( m , 3 ) = 1. Giả sử m > 1 xét hai trường hợp :
a. m = 3l + 1 ( l
*
∈
n

). Ta có :
k

n

1+2 +4 =1
+
n

k

23 (3l+1) + 43 = 1 + a

3l+1

+a

6l+2

( với a = 23 )

(3l+1)


n

3l

2

6l

2

2

suy ra 1 + 2 + 4 = a ( a - 1 ) + a ( a - 1 ) + a + a + 1  a +a + 1
n

n

⇒ 1 + 2 + 4 là hợp số.

b. m = 3l + 2 ( l  *).
∈
Ta có :
n

k

n

1+2 +4 =1+


23

(3l+2)

3
+ 4

(3l+2)

= 1 + a3l+2 + a6l+4
6l+3

=a(a

2

3l

2

2

- 1) + a ( a - 1) + a +a + 1  a +a + 1
k

( với a = 23 )
n

n


Suy ra 1 + 2 + 4 là hợp số.
k

Vậy m = 1 tức n = 3 .
Bài 3 :
a. Tìm số nguyên tố p sao cho :
p + 2 , p + 6 , p + 8 , p + 14 là những số nguyên tố.


b. Tìm 3 số nguyên tố liên tiếp p, q, r, sao cho p2 + q2
2
+ r
nguyên tố.
Giải :
a. Ta lần lượt xét các trường hợp :

cũng là số


+) p = 2 thì p + 2 = 4 là hợp số.
+) p = 3 thì p + 6 = 9 là hợp số.
+) p = 5 thì p + 2 = 7 ; p + 6 = 11; p + 8 = 13 ; p + 14 = 19 là những
số nguyên tố.
Vậy p = 5 là số cần tìm.
+) Với p > 5 thì p có dạng p = 5k ± 1; p = 5k ± 2 (* k∈  )
- Nếu p = 5k + 1 thì p + 14 = 5p + 15 = 5 ( k + 3 ) là hợp số.
- Nếu p = 5k – 1 thì p + 6

= 5k + 5 = 5 ( k + 1 ) là hợp số.


- Nếu p = 5k + 2 thì p + 8

= 5k + 10 = 5 ( k + 2 ) là hợp số.

- Nếu p = 5k – 2 thì p + 2

= 5k là hợp số.

Vậy tất cả các số nguyên tố lớn hơn 5 đều không thoả mãn.
Kết luận : p = 5 là số nguyên tố duy nhất cần tìm.
b. Tìm ba số nguyên tố liên tiếp p, q, r.
TH1 : p = 2 ; q = 3 ; r = 5
2

có p + q
2
+ r

2

= 4 + 9 + 25 = 38 không là số nguyên tố.

Vậy trường hợp 1 không thoả mãn.
TH2 : p = 3; q = 5; r = 7 thì p2 + q2
2
+ r
nguyên tố.

= 9 + 25 + 49 = 83 là số


Vậy trường hợp 2 thỏa mãn.
 TH3 : p, q, r là các số nguyên tố liên tiếp lớn hơn 3.
Do p, q, r đều nguyên tố nên chúng không chia hết cho 3.
Lúc đó p, q, r có dạng :
 p

= 3k
± 1


q
=

3l ± 1

( k, l, m ∈