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

CHINH PHỤC KỲ THI HỌC SINH GIỎI CẤP HAI

A. KiÕn thøc cÇn nhí

1. Định nghĩa số nguyên tố, hợp số.

1) Số nguyên tố là những số tự nhiên lớn hơn 1, chỉ có 2 ước số là 1 và chính nó.

Ví dụ: 2, 3, 5, 7, 11, 13, 17, 19....

2) Hợp số là số tự nhiên lớn hơn 1 và có nhiều hơn 2 ước.

Ví dụ: 4 có 3 ước số: 1 ; 2 và 4 nên 4 là hợp số.

3) Các số 0 và 1 không phải là só nguyên tố cũng không phải là hợp số.

4) Bất kỳ số tự nhiên lớn hơn 1 nào cũng có ít nhất một ước số nguyên tố.

2. Một số tính chất.

●Có vô hạn số nguyên tố.

• Nếu số nguyên tố p chia hết cho số nguyên tố q thì = p q .

• Nếu tích abc chia hết cho số nguyên tố p thì ít nhất một thừa số của tích abc chia hết cho

số nguyên tố p.

• Nếu a và b không chia hết cho số nguyên tố p thì tích ab không chia hết cho số nguyên

tố p .

●Nếu A là hợp số thì A có ít nhất một ước nguyên tố không vượt quá . A

Chứng minh. Vì n là hợp số nên n ab = với , ,1 a b a b n ∈ < ≤ <  và a là ước nhỏ nhất của .n

Thế thì 2. n a ≥ Do đó . a n ≤

3. Phân tích một số ra thừa số nguyên tố:

• Phân tích một số tự nhiên lớn hơn 1 ra thừa số nguyên tố là viết số đó dưới dạng một

tích các thừa số nguyên tố.

+ Dạng phân tích ra thừa số nguyên tố của mỗi số nguyên tố là chính số đó.

+ Mọi hợp số đều phân tích được ra thừa số nguyên tố, phân tích này là duy nhất nếu

không tính thứ tự các thừa số.

Chẳng hạn α β γ = A a .b ...c , trong đó a, b, c là các số nguyên tố và α β γ ∈ * , , ..., N

Khi đó số các ước số của A được tính bằng ( )( ) ( ) α β γ + + + 1 1 ... 1

Tổng các ước số của A được tính bằng

α β γ + + − − − − − −

+1 1 1 a 1 b 1 c 1 . ... a 1 b 1 c 1

CHỦ ĐỀ

3

SỐ NGUYÊN TỐ,

HỢP SỐ

TỦ SÁCH CẤP 2| 74

BỒI DƯỠNG HỌC SINH GIỎI CẤP 2 |

CHUYÊN ĐỀ SỐ HỌC

4. Số nguyên tố cùng nhau.

Hai số a và b nguyên tố cùng nhau khi và chỉ khi ( ) = a,b 1.

Các số a, b, c nguyên tố cùng nhau khi và chỉ khi ( ) = a,b,c 1.

Các số a, b, c đôi một nguyên tố cùng nhau khi và chỉ khi ( ) ( ) ( ) = = = a,b b,c c,a 1.

5. Cách nhận biết số nguyên tố.

Cách 1

Chia số đó lần lượt cho các số nguyên tố từ nhỏ đến lớn: 2; 3; 5; 7...

- Nếu có một phép chia hết thì số đó không là số nguyên tố.

- Nếu thực hiện phép chia cho đến lúc thương số nhỏ hơn số chia mà các phép chia vẫn có

số dư thì số đó là số nguyên tố.

Cách 2

- Một số có hai ước số lớn hơn 1 thì số đó không phải là số nguyên tố.

- Nếu A là hợp số thì A có ít nhất một ước nguyên tố không vượt quá . A - Với quy tắt trên trong một khoảng thời gian ngắn, với các dấu hiệu chia hết thì ta nhanh

chóng trả lời được một số có hai chữ số nào đó là nguyên tố hay không.

B. MỘT SỐ DẠNG TOÁN SỐ NGUYÊN TỐ, HỢP SỐ

 Dạng 1: Chứng minh một số là số nguyên tố hay hợp số

Bài toán 1. Nếu p và 2 8 p  là các số nguyên tố thì 2 2 p  là số nguyên tố.

Hướng dẫn giải

Xét 3 1 p k   ( k nguyên) thì 2 8 3 p , là hợp số.

Xét 3 2 p k   thì 2 8 3 p , là hợp số.

Vậy 3 p k  , mà p là số nguyên tố nên 3 p  .

Khi đó 2 2 11 p   , là số nguyên tố.

Bài toán 2. Chứng minh rằng 4 4 + n là một số nguyên tố khi 1. = n

Hướng dẫn giải

Ta có: ( ) ( ) 2 2 4 4 2 2 2 4 4 4 4 2 2 + = + + − = + − n n n n n n

( )( ) ( ) ( ) 2 2 2 2 2 2 2 2 1 1 . 1 1    = + − + + = − + + +    n n n n n n

Nếu 1 > n thì cả hai thừa số trên đều lớn hơn 1. Như vậy 4 4 + n là một số nguyên tố

khi 1. = n

Bài toán 3. Chứng minh rằng với mọi số tự nhiên 1 n > thì 5 4 1 n n + + là hợp số.

.75 | CHUYÊN ĐỀ SỐ HỌC