Một lớp học có 42 học sinh, muốn chia lớp thành các nhóm thuyết trình sao cho số học sinh ở mỗi nhóm bằng nhau và số tổ lớn hơn 1 và nhỏ hơn 10. Có thể chia được không nếu số học sinh trong lớp là 43?
Định nghĩa 1. Một số nguyên dương được gọi là số nguyên tố nếu số đó lớn hơn 1 và chỉ có hai ước dương là 1 và chính nó. Số nguyên dương lớn hơn 1 không phải là số nguyên tố được gọi là hợp số.
Chú ý: Hai số 0 và 1 không phải là số nguyên tố, cũng không phải là hợp số.
Ví dụ 1. Các số 2, 3, 5, 7, 11 là các số nguyên tố đầu tiên.
Các số 4, 6, 8, 9 là các hợp số
Tính chất 1. Với mỗi số tự nhiên $n \geq 2$ thì hoặc $n$ là số nguyên tố, hoặc $n$ là tích của các số nguyên tố.
Chứng minh
Ta chứng minh bằng quy nạp.
Với $n =2, 3$ ta có $n$ là một số nguyên tố.
Gỉa sử bài toán đúng với mọi $k$ với $k \leq n$. Ta chứng minh bài toán đúng với $n +1$.
Nếu $n+1$ là số nguyên tố, ta có điều cần chứng minh. Nếu $n+1$ không phải là số nguyên tố, khi đó $n+1$ có thể phân tích thành tích hai số $p$ và $q$ $ (2\leq p, q<n) $, tức là $n=p \cdot q$. Theo giả thiết quy nạp thì $p, q$ hoặc là nguyên tố hoặc là có thể phân tích thành tích các số nguyên tố. Từ đó ta có điều cần chứng minh.
Tính chất 2.
1) Hai số nguyên tố bất kì phân biệt là số nguyên tố cùng nhau.
2) Cho số nguyên tố $p$, nếu $a$ là một số nguyên thì hoặc $ p|a $ hoặc $(a,p)=1$.
3) Nếu $p$ là số nguyên tố và $p|ab$, khi đó $p|a$ hoặc $p|b$.
Chứng minh
1) Hiển nhiên theo định nghĩa số nguyên tố.
2) Đặt $d=(p,a)$. Ta có $d|a, d|p$. Vì $p$ nguyên tố nên $d=1$ hoặc $d=p$. Từ đó suy ra điều cần chứng minh.
3) Nếu $a$ không chia hết cho $p$, suy ra $(p,a)=1$, mà $p|ab$ nên ta có $p|b$.
Phân tích một số thành thừa số nguyên tố.
Định lý 18 cho ta thấy rằng mọi số nguyên dương lớn hơn hoặc bằng 2 có thể là số nguyên tố hoặc có thể phân tích thành tích các thừa số nguyên tố. Nhưng sự phân tích đó có duy nhất không? Để biết được điều đó, sau đây chúng tôi nêu ra một định lý quan trọng của số học và không chứng minh định lý này. Bạn đọc có thể tham khảo trong [1].
Định lý 2. (Định lý cơ bản của số học) Mọi số nguyên dương lớn hơn 1 đều có thể phân tích một cách duy nhất thành tích các số nguyên tố (không tính thứ tự sắp xếp các số thừa số nguyên tố)
Ví dụ 2. $ 12=2^2.3 ; 245=5.7^2 $
Hệ quả 1. Cho hai số nguyên $a$ và $b$. Giả sử $a,b$ được phân tích thành các thừa số nguyên tố $ a=p_1^{x_1}p_2^{x_2}…p_m^{x_m}.a’, b=p_1^{y_1}p_2^{y_2}…p_m^{y_m}.b’ $. Trong đó $(a’,b’)=1$, các thừa số $ p_i $ là các thừa số nguyên tố chung.
Đặt $ z_i=\min{x_1,y_1}; t_i=\max{x_1,y_1} $, khi đó $(a, b)=p_1^{z_1}p_2^{z_2}…p_m^{z_m} $ và $ [a,b]=p_1^{t_1}p_2^{t_2}…p_m^{t_m}.a’.b’ $
Ví dụ 3. Tìm ước chung nhỏ nhất và bội chung nhỏ nhất của hai số 252 và 220.
Lời giải. Ta có $ 252=2^2.3^2.7,220=2.3^3.5 $
Do đó ước chung nhỏ nhất của 252 và 220 là $ 2.3^3=18 $ và bội chung nhỏ nhất của 252 và 220 là $ 2.3^3.5.7 $.
Hệ quả 2. Cho số nguyên $a$ và số tự nhiên $n$. Giả sử $n$ được phân tích thành các thừa số nguyên tố $ n=p_1^{a_1}p_2^{a_2}…p_k^{a_k} $. Khi đó nếu $ a \vdots p_1^{a_1} \forall i=1,…,k $ thì $ a \vdots n $
Hệ quả 3. Mỗi số tự nguyên dương $n$ tồn tại duy nhất số không âm $m$ và $q$ trong đó $q$ lẻ và $n = q.2^m$.
Ví dụ 4. $48 = 3.2^4$, $15 = 15.2^0$.
Bài tập có lời giải.
Bài 1. Tìm các số nguyên tố $p$ để: $p+2$, $p+6$, $p+8$; $p+14$ cũng là các số nguyên tố.
Lời giải: Dễ thấy $p = 2, 3$ không thỏa đề bài, $p=5$ thỏa đề bài.
Xét $p>5$.
- Nếu $p = 5k+1$ thì $p+4$ chia hết cho $5$ và $p+4 > 5$ nên không là số nguyên tố.
- Nếu $p = 5k+2$ thì $p+8 = 5k+10$ chia hết cho 5, không là số nguyên tố.
- Nếu $p = 5k+3$ thì $p+2 = 5(k+1)$ chia hết cho 5, không là số nguyên tố.
- Nếu $p= 5k+4$ thì $p+6 = 5(k+2)$ chia hết cho 5, không là số nguyên tố.
Kết luận: $p=5$.
Bài 2. Tìm các số nguyên dương $n$ để $n^5+n+1$ là số nguyên tố.
Lời giải: Ta có $A(n) = n^5 + n+ 1 = n^5 – n^2 + n^2 + n +1 = n^2(n-1)(n^2+n+1) + (n^2+n+1) = (n^2+n+1)(n^3-n^2+1)$
Vì $n^2+n+1 >1$, nên $A(n)$ là số nguyên tố thì $n^3-n^2+1 = 1$, suy ra $n=1$
Thử lại $n=1$ thỏa đề bài.
Bài 3. Cho số tự nhiên $n$, chứng minh rằng nếu $ 2^n-1 $ là số nguyên tố thì n cũng là số nguyên tố.
Lời giải. Giả sử $n$ không là số nguyên tố.
- Với $n=0$ thì $2^0 – 1 = 0$ không là số nguyên tố.
- Với $n=1$ thì $2^1 – 1 = 0$ không là số nguyên tố.
- Với $n > 1$, $n = q \cdot q$ trong đó $1 < p, q < n$. Khi đó $2^n – 1 = (2^p)^q = 1$ chia hết cho $2^p-1$, mà $1 < 2^p-1 < 2^n-1$ nên $2^n-1$ không là số nguyên tố. (mâu thuẫn.
Vậy $n$ là số nguyên tố.
Bài 4. Cho các số nguyên dương $a, b, c, d$ thỏa $ac = bd$. Chứng minh rằng $a^2+b^2+c^2+d^2$ là hợp số.
Lời giải.
Đặt $d = UCLN(a,b)$, và $a = du, b = dv$, suy ra $(u,v) = 1$.
Khi đó ta có $uc = vd$, mà $u \mid vd, (u,v) = 1$, suy ra $u \mid d$, đặt $d = um$, suy ra $c = vm$.
Vậy $a + b+ c+ d = du + dv + vm + um = (u+v)(m+d)$, các số $d, m, u, v \geq 1$ nên $a+b+c+d$ là hợp số.
Bài tập rèn luyện.
Bài 1.
a) Chứng minh rằng mọi số nguyên tố lớn hơn 3 đều có dạng $ 3k+1 $ hoặc $ 3k-1(k\geq 2) $
b) Chứng minh rằng mọi số nguyên tố lớn hơn 5 đều có dạng $ 6k+1 $ hoặc $ 6k-1 (k\geq 2) $.
Bài 2. Chứng minh rằng $ n^4-1$ là hợp số với mọi số nguyên n>1.
Bài 3. Tìm số nguyên tố $p$ sao cho $p+2, p+4$ cũng là số nguyên tố.
Bài 4. Cho $n$ không phải là số nguyên tố. Chứng minh rằng nếu $p$ là ước nguyên tố lớn nhất của n thì $ p^2\leq n $.
Bài 5. Cho số nguyên tố $p$. Khẳng định sau đúng hay sai: “Nếu $ a|p(p-1) $ thì a|p hoặc a|(p-1)”.
Bài 6. Tìm tất cả các số tự nhiên $n$ lẻ để $n, n+10, n+14$ là số nguyên tố.
Bài 7. Tìm tất cả các số nguyên tố $p$ sao cho $ 2p^2+1 $ là số nguyên tố.
Bài 8. Tìm tất cả các số nguyên dương sao cho $ a^4+4b^4 $ là số nguyên tố.
Bài 9. Tìm tất cả các số nguyên tố p sao cho $ 2p^2+1 $ là số nguyên tố.
Bài 10. Chứng minh rằng nếu số nguyên dương $ n\geq 2 $ là số nguyên tố nếu nó không có ước nguyên tố nào nhỏ hơn hoặc bằng $ \sqrt n $
