Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố
1
ỦY BAN NHÂN DÂN TĨNH HÀ TĨNH
TRƯỜNG ĐẠI HỌC HÀ TĨNH
--------------------
Bµi TËp Lín
Bước đầu tìm hiểu và phân loại bài tập về số nguyên tố

Gv hướng dẫn: Ths NguyÔn ThÞ Thanh T©m
Sinh viên thực hiện: Ng« ThÞ Kim Nhung
NguyÔn Cao ThiÖn
Khoa Sư Phạm Tự Nhiên
Lớp K
2
Sư Phạm Toán
Hà Tĩnh 12/2010
Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố
2
Đồng tác giả
Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố
3
A - ĐẶT VẤN ĐỀ
I - Lý do chọn đề tài:
Toán học là công cụ giúp việc học tập các môn khác cả về kiến thức và t ư
duy. Môn toán có tiềm năng phát triển năng lực trí tuệ, rèn luyện tính linh
hoạt, độc lập, sáng tạo, tính chính xác, thẩm mỹ cùng sự kiên trì, nhẫn nại.
Trong chương trình toán học đa dạng và phong phú của nó, các bài toán về
"Số nguyên tố" luôn để lại những vấn đề mới mẻ cho người học.
"Toán học là bà hoàng của khoa họ c". "Số học là bà chúa của toán học".
Trong số học các bài toán hóc búa, thú vị hầu hết là bài toán về số nguyên tố.
Từ trước công nguyên, Ơclít đã khẳng định số nguyên tố là phạm trù c ơ

Phần hai: - Phân dạng bài toán
Dạng 1: Các bài toán về tập hợp số nguyên tố
Dạng 2: Chứng minh một số, một biểu thức là số nguyên tố, hợp số
Dạng 3: Tìm số x thõa mãn điều kiện cho trước
Dạng 4: Áp dụng giải phương trình nghiệm nguyên, chia hết
Dạng 5: Áp dụng, chứng minh một số bổ đề, định lí có ứng dụng tr ong giải
các bài toán về số nguyên tố
IV - Phương pháp nghiên c ứu
Nghiên cứu tài liệu
Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố
5
B – NỘI DUNG
Phần một: TÌM HIỂU CHUNG VỀ LÝ THUYẾT SỐ
NGUYÊN TỐ
Vấn đề số nguyên tố là một trong những vấn đề trung tâm của bộ môn số
học. Trong chương này ta sẽ tìm hiểu và bổ sung một số vấn đề trong lí thuyết
số: số nửa nguyên tố, số giả nguyên tố. Để đơn giản, chúng ta xét khái niệm số
nguyên tố trong tập hợp các số tự nhiên 
I - Số nguyên tố
1. Định nghĩa
Số nguyên tố là số tự nhiên chỉ chia hết cho một và chính nó.
2. Tập hợp số nguyên tố
2.1 Định lí 1:
Ước nhỏ nhất lớn hơn 1 của một số tự nhiên lớn h ơn 1 là một số nguyên
tố.
Chứng minh: (Bằng phản ch ứng)
Giả sử a

, a > 1 và p > 1: p là ư ớc nhỏ nhất của a thì p là một số
nguyên tố.

+ 1 là số tự nhiên lớn hơn 1 nên a có ít nhất một ước số
nguyên tố q.
Nhưng vì: Chỉ có hữu hạn số nguyên tố p
1
, p
2
,......, p
n
nên q phải trùng với
một trong các số p
1
, p
2
,......, p
n
. Do đó q phải là ước của tích p
1
p
2
....p
n
.
Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố
6
Từ q là ước của a = p
1
p
2
....p
n

II - Định lí cơ bản của số học
Trong mục này chúng ta sẽ chứng minh một định lí nói lên vai trò quan
trọng của số nguyên tố trong tập hợp số tự nhiên N. Định lí này có nhiều ứng
dụng. Để thuận lợi cho việc chứng minh tr ước hết ta chứng minh một số bổ đề
sau đây.
1) Các bổ đề:
1.1 Bổ đề 1: Với số tự nhiên a và số nguyên tố p thì hoặc a nguyên tố
cùng nhau với p hoặc a chia hết cho p.
Chứng minh:
Giả sử: d = ƯCLN(a,p)

d\p






pd
d 1
(a

, p là số nguyên tố)
1.2 Bổ đề 2: Nếu một tích gồm nhiều số tự nhiên chia hết cho số nguyên
tố p thì phải có ít nhất một thừa số của tích chia hết cho p
Chứng minh:
Thật vậy:
Giả sử các số tự nhiên không chia hết cho số nguyên tố p.
Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố
7

- Nếu a
1
= 1 thì a = p
1
đó là sự phân tích a thành th ừa số nguyên tố.
- Nếu a
1
> 1 thì a
1
phải có một ước nguyên tố p
2
chẳng hạn và ta có:
a
1
= p
1
a
2
nên a = p
1
p
2
a
2
1

a
2
< a
1

2
....p
n
= q
1
q
2.
...q
n
là 2 dạng phân tích của a thành số
nguyên tố.
Thế thì ta có: p
1
\q
1
q
2.
...q
n
Do đó p
1
phải là ước của một thừa số nào đó
chẳng hạn q
1
của tích q
1
q
2.
...q
n

...p
n
= 1 nên ta được m = n và p
i
= q
i
, i =
n,1

tính duy nhất được
chứng minh.
Ví dụ: Phân tích a = 300; a =300 = 2.2.5.5.3
3) Ứng dụng
3.1 Tìm ước số
- Cho a = p
1
1

p
2
2

... p
n
n

(

i
, p

1

p
2
2

... p
n
n

với 0


i
,

i

b = p
1
1

p
2
2

... p
n
n


... p
n
n

với

i
= max(

i
,

i
)
Do đó (a,b).[a,b] = ab
Tính số các ước của một số tự nhiên
- Với a =1 thì
)(a
= 1
- Với a >1 Giả sử a = p
1
1

p
2
2

... p
n
n

1
1

p
2
2

... p
n
n

thì
)(a
=
1
1
1
11
1



p
p

1
1
2
12
2

khác nhau của a và

i
(1

i

k) là số các nhân tử cùng là p
i
trong sự phân
tích a thành thừa số nguyên tố, ta sẽ có a = p
1
1

p
2
2

... p
k
n

gọi là dạng phân tích
tiêu chuẩn của a.
VD 300 = 2
2
.5
2
.3
III - Một số vấn đề về số nguyên tố

- Dạng khác của định lí Fermat:
Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố
10
Nếu p là số nguyên tố a là số n guyên bất kỳ, a
p
– a sẽ chia hết p. Nghĩa là
a
p

a (mod p)

Định lí nhỏ Fermat là c ơ sở để kiểm tra tính nguyên tố theo xác suất
trong kiểm tra Fermat.
2.2 Số giả nguyên tố (Fermat) mạnh
Định nghĩa: Trong đồng dư thức của định lí nhỏ Fermat vớ i số nguyên tố
lẻ p và số tự nhiên a không chia hết cho p
a
p – 1

1 (mod p)
ta phân tích số chẵn p – 1 = 2
s
m, với m là số lẻ
Khi đó: - Hoặc a
m

1 (mod p) (1)
- Hoặc a
m
s

Fermat với mọi cơ sở a sao cho ƯCLN [a,n] = 1.
4) Nếu n < 4759123141 là hợp số thì n không thể là số giả nguyên tố mạnh
Fermat đồng thời với ba cơ sở a = 2, 7 và 61 (Jaeschhe – 1993).
5) Nếu n < 341550071728312 là hợp số thì n không thể là số giả nguyên tố
mạnh Fermat đồng thời với bảy cơ sở a = 2, 3, 5, 7, 11, 13 và 17 (Jaeschhe –
1993).
Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố
11
2.3 Số giả nguyên tố Euler
Định nghĩa:
Số tự nhiên lẻ n thỏa mãn đồng dư thức tương tự với một a nào đó
a
2
1n


1 (mod n) được gọi là số nguyên tố xác suất Euler
Nếu n là hợp số thì n được gọi là số giả nguyên tố Euler
2.4 Số giả nguyên tố Euler – Jacobi
Định nghĩa:
Định lí Euler khẳng định: Với mọi số nguyên tố p và mọi số a
a
2
1p

(
p
a
) (mod p)
Trong đó: (

+ n

3 (mod 4)
+ Kí hiệu Jacobi (
n
a
) = – 1
3) Số nguyên tố Pamanujan
Định nghĩa:
- Số nguyên tố Ramanujan là các số R
n
sao cho R
n
là số nhỏ nhất thỏa mãn
®iều kiện π(x) − π(x \ 2) ≥ n, cho mọi x ≥ R
n.
- Hoặc số nguyên tố Ramanujan là các số Nguyên R
n
sao cho R
n
là số nhỏ
nhất có thể bảo đảm có n số nguyên tố giữa x và x\2 với mọi x ≥ R
n
Vì R
n
là số nguyên tố nhỏ nhất thỏa mãn điều kiện trên nên R
n
phải là số
nguyên tố
Mỗi khi hàm π(x) − π(x\2) tăng lên 1 đó là do có thêm một số nguyên tố

tập tương tự.
Dạng 1: Các bài toán về tập hợp số nguyên tố
Loại 1: Tìm tập hợp số nguyên tố
Để giải quyết các bài toán dạng này ta cần vận dụng linh hoạt các
tính chất của số nguyên tố, nhiều trường hợp ta kèm theo phương pháp
chứng minh phản chứng.
Bài toán 1: Tập hợp các số nguyên tố là vô hạn
Cách 1: Cho n

, n > 2. Chứng minh n! – 1 có ít nhất một ước
nguyên tố lớn hơn n. Từ đó suy ra không tồn tại số nguyên tố lớn nhất.
- Gọi a = n! – 1. Do n > 2 nên a > 1
Mọi số tự nhiên lớn hơn 1 đều có ít nhất một ước nguyên tố.
Gọi p là ước nguyên tố của a. Ta sẽ chứng minh p > n
Thật vậy: Giả sử p

n thì tích 1.2.3......n chia h ết cho p
Ta có n!

p mà a

p

1\p

vô lý

p > n
- Giữa n! – 1 và n có ít nhất 1 số nguyên tố. Gọi số đó là q
Giả sử n là số nguyên tố lớn nhất suy ra n > 2

2
n
)
2
r
+ 1
Đặt a = 2
2
n
+ 1 ta có: b = (a – 1)
2
r
+ 1 = ak + Z, k

(Sau khi khai triển nhị thức (a – 1)
2
r
)
Từ đó (a,b) = (a,2) = 1 do a là s ố lẻ.
Gọi p
n
là số nguyên tố nhỏ nhất của 2
2
n
+ 1 (n

Z
*
)
Theo chứng minh trên p

1.
p
2
....p
k
> 2
Với mọi giá trị k nguyên sao cho 1 < k < m thì k đều có ước nguyên
tố p
i
nào đó nên (k,m)

1. Từ đó

)(m
= 1 (vì chỉ có (1,m) = 1)
Vậy có vô số số nguyên tố.
Bài toán 2: Có tồn tại 1000 số tự nhiên liên tiếp đều là hợp số không?
Gọi A = 2.3.4.........1001 khi đó
Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố
15
Các số A + 2, A + 3,......, A + 1001 là 1000 số tự nhiên liên tiếp, rõ
ràng các số đó là hợp số

Có tồn tại 1000 số tự nhiên liên tiếp đều là
hợp số.
Bài toán 3: Chứng minh mọi số nguyên tố p đều có dạng 3k

1
(k


2
n n 
p
*) n = 2

p = 2, n = 3

p = 5 thỏa mãn.
*) n > 3 thế thì hoặc n – 1 chẵn hoặc n + 2 chẵn nên p là hợp số.

Giá trị p cần tìm là p = 2 hoặc p = 5.
Các bài tập tương tự:
1. Chứng minh rằng với m > 2 giữa m và m! c ó ít nhất một số nguyên
tố. Từ đó suy ra rằng có vô số số nguyên tố.
2. (Iran 2008) Chứng minh rằng tồn tại vô hạn số nguyên tố p thỏa
mãn 13 \(p
3
+ 1)
3. Chứng minh rằng:
a) Mọi số nguyên tố lớn hơn 2 đều có dạng 4p

1 (p > 0)