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ố.
Thật vậy: p
P
p phải là hợp số nghĩa là p
1
\p và 1< p
1
< p.
Suy ra p
1
\a mà 1< p
1
< p
mâu thuẫn (do p là ước nhỏ nhất lơn 1 của a)
2.2 Định lí Ơclit: Tập hợp số nguyên tố là v ô hạn
Chứng minh:
Giả sử chỉ có hữu hạn số nguyên tố p
1
= 2, p
2
= 3, , p
n
Xét a = p
1
p
2
p
n
+ 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
+ 1 và q lại là ước của p
1
p
2
p
n
suy ra q là
ước của a – p
1
p
2
p
n
= 1. Mâu thuẫn với giả thiết q là số nguyên tố. Vậy t ập
hợp số nguyên tố là vô hạ n (đpcm).
3. Tính chất của số nguyên tố
1) Nếu một số nguyên tố p chia hết cho số nguyên tố a khác 1 thì a = p
2) Nếu các số nguyên tố p
1
, p
2
, , p
n
(n ≥ 2) khác nhau từng đôi một thì
chúng nguyên tố cùng nhau.
3) 2 là nguyên tố chẵn nhỏ nhất cũng là số nguyên tố chẵn duy nhất.
4) Nếu p là số nguyên tố, a là số nguyên suy ra hoặc p \a hoặc (a,p) = 1
5) Ước số dương bé nhất khác 1 của một hợp số a là một số nguyên tố
không vượt quá
a
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
Theo bổ đề 1 chúng đều nguyên tố cùng nhau với p. Do đó ta có tích các
số tự nhiên nguyên tố cùng nhau với p chứ không phải chia hết p. Mâu thuẫn
với giả thiết rằng p là ước của tích đó.
1.3 Hệ quả: Nếu số nguyên tố p là ước của tích các thừa số nguyên tố q
1
,
q
2
, , q
n
thì p phải trùng với một số trong các số nguyên tố của tích đó.
2) Định lí cơ bản
Mỗi số tự nhiên lớn hơn 1 đều phân tích được thành 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 đó a có một ước nguyên tố p
1
nào đó
Ta có: a = a
1
p
1
trong đó 1
a
1
< a
- 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
+) Nếu a
2
= 1 thì a = p
1
p
2
là sự phân tích a thành thừa số nguyên tố
+) Nếu a
2
> 1 thì với lập luận như trên ta được thừa số nguyên tố p
3
, quá
trình đó phải kết thúc vì ta có a > a
1
> a
2
> nên ắt phải có a
n
= 1 ta được
p
1
p
2
p
n
là dạng phân tích của a thành lũy thừa số nguyên tố
b) Tính duy nhất
Giả sử ta có: a = p
1
p
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
. Vậy ta có p
1
= q
1
và ta được p
2
p
3
p
n
=
q
2
q
3.
q
n
Lập lại lý luận trên với p
2
, p
3
cho tới khi đã ước lược hết các thừa số
nguyên tố của một vế trong đẳng thức trên, vì không thể xảy ra 1 = q
n+1
q
m
Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố
8
hoặc p
m+1
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
i
)
d\a
d = p
1
1
p
2
2
p
n
n
Với 0
i
i
- Cho (a,b) = 1 khi đó d\ab
d\xy với (x,y) = 1
3.2 Tìm ƯCLN, BCNN
Giả sử a = p
1
1
p
2
2
p
n
n
với 0
i
,
i
b = p
1
1
p
2
2
p
n
n
Khi đó (a,b) = p
1
1
p
2
2
p
n
n
với
i
= min(
i
,
i
)
[a,b] = p
1
1
p
2
2
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
(
i
)
Muốn xác định số các ước của a cho
i
lần lượt các giá trị từ 0 đến
i.
. Số
các ước số của a là
)(a
= (
1
+ 1)(
2
+ 1) (
n
+ 1)
3.4 Tìm tổng 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
thì
)(a
=
1
1
1
11
1
p
p
1
1
2
12
2
p
p
1
1
1
n
n
n
p
p
4) Dạng phân tích tiêu chu ẩn
Trong sự phân tích số 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 p
1
, p
2
, , p
n
là các ước nguyên tố đôi một
Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố
9
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ố
Trong mục này chúng ta sẽ bổ sung thêm một số vấn đề về số số nguyên tố
như số nửa nguyên tố, số giả nguyên tố, một vài vấn đề tìm biểu thức lấy các
giá trị là số nguyên tố và một số vấn đề khác.
1) Số nửa nguyên tố
- Số nửa nguyên tố là số tự nhiên được tạo thành từ tích của hai số nguyên
tố (không nhất thiết phải phân biệt)
Ví dụ: các số nửa nguyên tố đầu tiên 4, 6, 9, 14, 15, 21, 15
- Tính đến nay, số nửa nguyên tố lớn nhất được biết đến là (2
43112609
– 1)
2
,
với hơn 25 triệu chữ số. Nó là bình phương của số nguyên tố lớn nhất được
biết. Bình phương của bất kì số nguyên tố nào cũng là số nửa nguyên tố, do đó
số nửa nguyên tố tiếp theo được biết đến vẫn sẽ là bình ph ương số nguyên tố
lớn nhất được biết (trừ khi tìm ra được một phương pháp khẳng định một số
lớn là số nửa nguyên tố mà không biết hai phần tử của nó).
- Giá trị của phi hàm Euler cho số nửa nguyên tố n = pq khi p và q phân
biệt là:
)(a
= (p – 1)(q – 1) = pq – (p + q) + 1 = n – (p + q) + 1
2) Số giả nguyên tố
2.1 Số giả nguyên tố Fermat
- Định nghĩa:
Định lí nhỏ Fermat khẳng định: Với mọi số nguyên tố p và số tự nhiên a
không chia hết cho p ta có:
a
p - 1
1 (mod p)
- 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
2
– 1 (mod p) với k nào đó
{0,1, s} (2)
Số tự nhiên lẻ n trong đó n – 1 = 2
s
m thỏa mãn a
m
– 1 (mod m) hoặc tồn
tại k
{0, 1, , s} sao cho a
m
s
2
– 1 (mod m) được gọi là số nguyên tố xác
suất mạnh Fermat cơ sở a.
Nếu n là hợp số thì n được gọi là số giả nguyên tố Fermat c ơ sở a.
* Số nguyên tố xác suất Fermat mạnh được sử dụng trong kiểm t ra Miller -
Rabin để kiểm tra tính nguyên tố theo xác suất của số tự nhiên lẻ.
Nhận xét:
1) Nếu n là số giả nguyên tố c ơ sở 2 thì m = 2
n
– 1 cũng là số giả nguyên
tố cơ sở 2. Từ đó suy ra có vô hạn số nguyên tố cơ sở 2.
2) Mọi số giả nguyên tố mạnh Fermat đều là số giả nguyên tố Fermat.
3) Số Carmichael: Hợp số n là số Carmichael nếu nó là số giả nguyên tố
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
1n
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
1p
(
p
a
) (mod p)
Trong đó: (
p
a
) là kí hiệu Legendre (chỉ được định nghĩa cho nguyên tố p).
Khi mở rộng kí hiệu Legendre cho số tự nhiên lẻ n và số tự nhiên a ta có kí
hiệu Jacobi được kí hiệu giống như kí hiệu Legendre: (
n
a
).
Số tự nhiên lẻ n thỏa mãn đồng dư thức tương tự định lí Euler:
a
2
1n
(
n
a
) (mod n)
Với a nào đó được gọi là số nguyên tố xác suất Euler – Jacobi cơ sở a. Nếu
n là hợp số thỏa mãn đồng dư thức trên thì nó được gọi là số giả nguyên tố
Euler – Jacobi cơ sở a.
Nhận xét:
1. Mọi số giả nguyên tố Euler c ơ sở a đều là số giả nguyên tố Fermat
2. Mọi số giả nguyên tố Euler – Jacobi cơ sở a đều là số giả nguyên tố
Euler cơ sở a.
3. Mọi số giả nguyên tố Fermat mạnh c ơ sở a đều là số giả nguyên tố
Euler – Jacobi.
4. Mọi số giả nguyên tố Euler – Jacobi cơ sở a thỏa mãn một trong hai
điều kiện sau là số giả nguyên tố mạnh c ơ sở a.
Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố
12
+ 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ố
nữa.
4) Số nguyên tố Mersenne
Định nghĩa:
Số nguyên tố Mersenne là một số có dạng lũy thừa của 2 trừ 1: 2
n
− 1 với
n là số nguyên tố
Ví dụ: 31 là số nguyên tố Mersenne M
n
= 31 = 2
5
– 1 với 5 là số nguyên tố
Điều kiện cần để M
n
là số nguyên tố là n là số nguyên tố, 2
4
– 1 = 15 là
hợp số vì 4 không là nguyên tố, nh ưng ngược lại không đúng: ví dụ số
Mersenne 2047 = 2
11
− 1 không là nguyên tố vì nó chia hết cho 89 và 23, mặc
dù số 11 là số nguyên tố.
Hiện nay, các số nguyên tố lớn nhất được tìm thấy thường là số
nguyên tố Mersenne.
Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố
13
Phần hai: PHÂN DẠNG BÀI TOÁN VỀ SỐ
NGUYÊN TỐ
Trong chương này chúng ta s ẽ phân dạng các bài toán về số nguyên
tố cùng một số phương pháp giải, bài tập ứng dụng và đưa ra một số bài
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
Theo chứng minh trên thì tồn tại q nguyên tố n < q < n! – 1
p > n
không tồn tại số nguyên tố lớn nhất
tập hợp số nguyên
tố là vô hạn.
Cách 2: Cho hai số tự nhiên m
n.
Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố
14
Chứng minh rằng 2
2
m
+ 1 và 2
2
n
+ 1 nguyên tố cùng nhau. Từ đó suy
ra tập hợp các số nguyên tố là vô hạn.
- Giả sử m > n. Đặt m = n + r, r
N
*
khi đó:
b = 2
2
m
+ 1 = (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
m
p
n
nm
. Vậy dãy số (p
n
) n
N là đôi
một khác nhau
Tập các số nguyên tố là vô hạn.
Cách 3: Chứng minh có vô số số nguyên tố bằng cách dựa vào số ước
số nguyên tố của một số.
Trước hết ta chứng minh với m > 2 ta có
)(m
> 1, từ đó suy ra có vô
số số nguyên tố. Với m > 2
m – 1 > 1 và (m – 1,m) = (m,1) = 1. Do đó
)(m
> 1
Giả sử chỉ có k số nguyên tố p
1
, p
2
, , p
k
Đặt m = 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 đó
Không có nhận xét nào:
Đăng nhận xét