Category Archives: Chuyên đề

Phương pháp chứng minh chia hết – P4 – Nguyên lý Dirichlet

Leave a reply

Nguyên lý Dirichlet có nhiều ứng dụng trong toán học được phát biểu một cách đơn giản như sau: Nếu có $n+1$ con thỏ cho vào $n$ cái chuồng thì có một chuồng chứa ít nhất hai con thỏ.

Nếu áp dụng vào số học ta sẽ có phát biểu tương tự: Có $n+1$ số nguyên khi chia cho $n$ thì sẽ có hai số nào đó có cùng số dư khi chia cho $n$, hay có hai số mà hiệu của chúng sẽ chia hết cho $n$.

Trong bài này chúng ta sẽ sử dụng tích chất này để giải các bài toán về chia hết.

Ví dụ 1. Chứng minh rằng trong 11 số chính phương có hai số mà hiệu của chúng chia hết cho 20.

Lời giải

Theo nguyên lý Dirichlet thì trong 11 số chính phương có hai số có hiệu chia hết cho 10. Giả sử đó là $a$ và $b$.

Ta có $a = m^2, b = n^2$ và $a-b = m^2-n^2$ chia hết cho 10. Khi đó $m, n$ cùng tính chẵn lẻ, suy ra $m^2-n^2 = (m-n)(m+n)$ chia hết cho 4.

Do đó $a-b = m^2-n^2$ chia hết cho 5, 4 nên chia hết cho 20.

Ví dụ 2. Với 4 số nguyên $a, b, c, d$.

Chứng minh rằng $(a-b)(a-c)(a-d)(b-c)(b-d)(c-d)$ chia hết cho 12

Lời giải

Đặt $A = (a-b)(a-c)(a-d)(b-c)(b-d)(c-d)$, ta chứng minh $A$ chia hết cho 3, 4.

  • Trong bốn số $a, b, c, d$ có hai số có cùng số dư khi chia cho 3, hay có hai số có hiệu chia hết cho 3. Do đó $A$ là tích các hiệu của hai số bất kì, nên $A$ chia hết cho 3.
  • Trong 4 số nếu có 3 số chẵn, hoặc 3 số lẻ, giả sử $a, b, c$ cùng tính chẵn lẻ, khi đó $(a-b)(b-c)$ chia hết cho 4. Do đó $A$ chia hết cho 3.
    • Nếu có hai số chẵn, hoặc hai số lẻ giả sử cặp $(a, b)$ và cặp $(c,d)$ cùng tính chẵn lẻ. Khi đó $(a-b)(c-d)$ chia hết cho 4. Do đó $A$ chia hết cho 4.
  • Vậy $A$ chia hết cho 12.

Ví dụ 3. Chứng minh rằng
a) rong 5 số nguyên thì có 3 số có tổng chia hết cho 3.
b) Trong 17 số nguyên thì có 9 số có tổng chia hết cho 9.

Lời giải

a) Một số khi chia cho 3 có các số dư là 0, 1, 2.

  • Nếu 5 số khi chia cho 3 có 1 hoặc 2 số dư, khi đó sẽ có 3 số có cùng số dư khi chia cho 3, tổng 3 số này sẽ chia hết cho 3.
  • Nếu 5 số khi chia cho 3 có đủ 3 số dư 0, 1, 2 thì tổng ba số có số dư khác nhau sẽ chia hết cho 3.
  • Vậy trong 5 số thì có 3 số có tổng chia hết cho 3.

b)  Gọi 17 số đó là $a_1, a_2, \cdots, a_{16}, a_{17}$.

Theo câu a) trong 5 số $a_1, \cdots, a_5$ có 3 số có tổng chia hết cho $3$, giả sử 3 số đó là $a_1, a_2, a_3$.

Đặt $b_1 = \dfrac{1}{3}(a_1+a_2+a_3)$.

Tương tự trong các số $a_4, a_5, \cdots, a_8$, có 3 số có tổng chia hết cho 3, giả sử là $a_4, a_5, a_6$.

Đặt $b_2 = \dfrac{1}{3}(a_4+a_5+a_6)$.

Tương tự ta sẽ có b_3, b_4.

Cuối cùng, còn 5 số $a_{13}, a_{14}, \cdots a_{17}$ có 3 số có tổng chia hết cho 3, giả sử là $a_{14}, a_{15}, a_{16}$.

Đặt $b_5 = \dfrac{1}{3}(a_{14} +a_{15} + a_{16})$.

Ta thấy các số $b_1, b_2, \cdots, b_5$ là các số nguyên, do đó áp dụng câu a) có 3 số có tổng chia hết cho 3, giả sử là $b_1, b_2, b_3$, tức là $b_1+b_2+b_3$ chia hết cho 3.

Từ đó ta có $a_1 + a_2 +\cdots +a_8+a_9$ chia hết cho 9.

Ví dụ 4. Chứng minh rằng trong 100 số phân biệt, luôn có một số hoặc một tổng vài số chia hết cho 100.

Lời giải

Ta xét các tổng sau

$S_1 = a_1$

$S_2 = a_2$

…

$S_{100} = a_1 + a_2 + \cdots +a_{100}$

Nếu trong các số $S_1, S_2, \cdots, S_{100}$ có một số chia hết 100 thì ta có điều cần chứng minh.

Nếu không có số nào chia hết cho 100 thì các số dư khi chia cho 100 là từ 1 đến 99, do đó tồn tại $i>j$ sao cho $S_i – S_j$ chia hết cho 100, hay $a_{j+1} + \cdots+a_i$ chia hết cho 100.

Do đó ta có điều cần chứng minh.

Bài tập rèn luyện

Bài 1. Chứng minh rằng tồn tại các số chỉ toàn chữ số 1 và chia hết cho 2019.

Bài 2. Chứng minh rằng mỗi tập con có $n+1$ phần tử của tập ${1, 2, \cdots, 2n}$ có hai số mà số này chia hết cho số kia.

Phương pháp chứng minh chia hết – P3

Leave a reply

Tiếp theo là phương pháp sử dụng đồng dư để chứng minh các bài toán chia hết.

Một số tính chất về đồng dư các bạn có thể xem lại từ bài giảng đồng dư

Sau đây ta xét một vài ví dụ sau.

Ví dụ 1. Chứng minh rằng với mọi số tự nhiên $n$:
a) $A = 7 \cdot 5^{2n} + 12 \cdot 6^n$ chia hết cho 19.
b) $5^{2n+1}+2^{n+4} + 2^{n+1}$ chia hết cho 23.

Lời giải

a) $5^{2n} = 25^n \equiv 6^n (\mod 19) \Rightarrow 7 \cdot 5^{2n} = 7 \cdot 6^n (\mod 19)$

Suy ra $ 7 \cdot 5^{2n} + 12 \cdot 6^n \equiv 19 \cdot 6^n \equiv 0 (\mod 19)$.

Do đó $A = 7 \cdot 5^{2n} + 12 \cdot 6^n$ chia hết cho 19.

b) Ta có $5^{2n+1}= 5 \cdot 25^n \equiv 5 \cdot 2^n (\mod 23)$.

Khi đó $5^{2n+1}+2^{n+4} + 2^{n+1} \equiv 5 \cdot 2^n + 16 \cdot 2^n + 2 \cdot 2^n (\mod 23)$

$\equiv 23 \cdot 2^n (\mod 23) \equiv 0 (\mod 23)$.

Do đó $5^{2n+1}+2^{n+4} + 2^{n+1}$ chia hết cho 23.

Ví dụ 2. Tìm tất các số $n$ để
a) $2^{2n} + 2^n + 1$ chia hết cho 5.
b) $2^n+ 1$ chia hết cho 9.

Lời giải

a) Ta thấy $16\equiv 1 (\mod 5)$, suy ra $16^n \equiv 1 (\mod 5)$.

Suy ra $2^{4k+r} \equiv 2^r (\mod 5)$.

Do đó ta xét $n$ theo moldun 4.

  • Nếu $n= 4k$, ta có $2^{2n} + 2^n + 1 \equiv 3 (\mod 5)$.
  • Nếu $n = 4k+1$ ta có $2^{2n} + 2^n + 1 \equiv 7 (\mod 5)$.
  • Nếu $n=4k+2$ ta có $2^{2n} + 2^n + 1 \equiv 4 (\mod 5)$.
  • Nếu $n=4k+3$ ta có $2^{2n} + 2^n + 1 \equiv 1 (\mod 5)$.

Vậy không tồn tại số tự nhiên $n$ để $2^{2n} + 2^n + 1$ chia hết cho 5.

b) Ta có $2^6 \equiv 1 (\mod 9)$, suy ra $2^{6k+r} equiv 2^r (\mod 9)$.

Đặt $n= 6k+r (0 \leq r \leq 5)$. Khi đó $2^n+1 \equiv 2^{6k+r}+1 \equiv 2^r + 1 (\mod 9)$

Do đó $2^n + 1$ chia hết cho 9 khi và chỉ khi $2^r+1$ chia hết cho 9, tìm ra được $r = 3$.

Vậy $n=6k+3$ với $k$ là số tự nhiên.

Ví dụ 3. Cho $a_n = 2^{2n+1} + 2^{n+1} + 1$ và $b_n = 2^{2n+1} – 2^{n+1} + 1$. Chứng minh rằng với mỗi số tự nhiên $n$, có một và chỉ một trong hai số $a_n, b_n$ chia hết cho 5.

Lời giải

Ta cần chứng minh $a_nb_n$ chia hết cho 5 và $a_n+ b_n$ không chia hết cho 5 với mọi $n$.

  • $a_n\cdot b_n = 2^{4n+2} + 1 \equiv 0 (\mod 5)$.
  • $a_n + b_n = 2^{2n+2} + 2 \equiv 4(-1)^n + 2  (\mod 5) \equiv 1, -2 (\mod 5)$.

Do đó $a_nb_n$ chia hết cho 5 và $a_n+b_n$ không chia hết cho 5.

Do đó có một và chỉ một trong hai số $a_n$ hoặc $b_n$ chia hết cho 5.

Ví dụ 4. (PTNK 2019) Cho $ A_n = 2018^n + 2032^n – 1964^n – 1984^n $ với $ n $ là số tự nhiên.
a) Chứng minh với mọi số tự nhiên $ n $ thì $ A_n $ chia hết cho $ 51 $.
b) Tìm tất cả những số tự nhiên $ n $ sao cho $ A_n $ chia hết cho $ 45. $

Lời giải

a) Do $ 2018 \equiv 1964 \quad \text{(mod 3)} \Rightarrow 2018^n \equiv 1964^n \quad \text{(mod 3)} . $
$ 2032 \equiv 1984 \quad \text{(mod 3)} \Rightarrow 2032^n \equiv 1984^n \quad \text{(mod 3)} $.
$ \Rightarrow A_n \ \vdots \ 3. $
Ta lại có $ 2018 \equiv 1984 \quad \text{(mod 17)} \Rightarrow 2018^n \equiv 1984^n \quad \text{(mod 17)} $.
$ 2032 \equiv 1964 \quad \text{(mod 17)} \Rightarrow 2032^n \equiv 1964^n \quad \text{(mod 17)} $.
$ \Rightarrow A_n \ \vdots\ 17. $
Do $ (3; 17) = 1 $ nên $ A_n \ \vdots \ 51 \quad \forall n$
b) $ A_n = 2018^n + 2032^n – 1964^n – 1984^n. $

b)

  • Ta xét các trường hợp của $ n $ để $ A_n \ \vdots \ 5. $
    Ta có $ A_n \equiv (-2)^n + 2^n -2\cdot(-1)^n $ (mod 5).
    Do đó nếu $ n $ lẻ $ \Rightarrow A_n \equiv 2 \quad $(mod 5)$ \quad \text{(loại)}$.
    Nếu $ n = 4k \Rightarrow A_n \equiv 2\cdot 2^{4k} -2 \equiv 2-2 \equiv 0 \quad$ (mod 5) (nhận)
    Nếu $ n = 4k + 2 \Rightarrow A_n \equiv 2\cdot 2^{4k+2} -2 \equiv 8 – 2 \equiv 6$ (mod 5) (loại).
    Vậy $ A_n \ \vdots \ 5 \Leftrightarrow n \ \vdots \ 4. $
  • Ta xét các trường hợp của $ n $ để $ A_n \ \vdots \ 9. $
    Ta có
    $A_n \equiv 2^n + (-2)^n – 2^n – 4^n \quad  (\mod 9)$
    $\equiv 2^n -4^n \quad \text { (mod 9) \quad (Do $n$ chẵn).}$
    $ \equiv 2^n(1-2^n) \quad \mod 9) Vì $ (2;9 ) = 1 \Rightarrow 2^n – 1  \vdots \ 9$.
    Xét $ n= 3k $ với $ k \in \mathbb{N} $. Ta có $ A_n \equiv 2^{3k} – 1 \equiv (-1)^k – 1 \quad (\mod 9) \Rightarrow k$ chẵn.

    • Xét $ n= 3k + 1 $ với $ k \in \mathbb{N} $. Ta có $ A_n \equiv 2^{3k + 1} – 1 \equiv 2\cdot(-1)^k – 1 \quad \text { (mod 9) \quad (loại)}. $
    • Xét $ n= 3k + 2 $ với $ k \in \mathbb{N} $. Ta có $ A_n \equiv 2^{3k + 2} – 1 \equiv 4\cdot(-1)^k – 1 \quad \text { (mod 9) \quad (loại)}. $
  • Vậy $ A_n \ \vdots \ 45 \Leftrightarrow n \ \vdots \ 12. $

Bài tập rèn luyện

Bài 1. Cho $n$ là số tự nhiên. Chứng minh rằng:
a) $5^{2n+1}+2^{n+4}+2^{n+1}$ chia hết cho $23$;
b) $11^{n+2}+12^{2n+1}$ chia hết cho $133$;
c)  $5^{n+2}+26.5^n+8^{2n+1}$ chia hết cho $59$;
d)  $5^{2n+1}.2^{n+2}+3^{n+2}.2^{2n+1}$ chia hết cho $38$.

Bài 2. Tìm tất cả các số tự nhiên $n$ sao cho:
a) $2^{3n+4}+3^{2n+1}$ chia hết cho 19
b) $n.2^n+ 1$ chia hết cho 3
c) $2^2n+2^n+1$ chia hết cho 21
d)  $1^n+ 2^n+ 3^n+ 4^n$ chia hết cho 5

Bài 3. Cho $n$ là số tự nhiên. Chứng minh rằng:
a)  $2^{2^{2n}}+10$ chia hết cho $13$;
b) $3^{2^{4n+1}}+2^{3^{4n+1}}+5$ chia hết cho $22$.

Bài 4. (PTNK) Tìm các số nguyên dương $n$ sao cho:
a) $n.2^n+3^n$ chia hết cho $5$;
b) $n.2^n+3^n$ chia hết cho $25$.

Phương pháp chứng minh chia hết – P2

Leave a reply

Phương pháp biến đổi thành tổng. 

Chú ý tính chất sau: $A, B$ chia hết cho $M$ thì $xA + yB$ chia hết cho $M$ với mọi $x, y$ nguyên.

Ví dụ 1. Chứng minh rằng nếu $4x-y$ chia hết cho 3 thì $A=4x^2 – 16xy-2y^2$ chia hết cho 9.

Lời giải
  • $x+2y = 4x-y -3(x-y)$ chia hết cho 3.
  • $4x^2-16xy-2y^2= (4x-y)(x+2y)+9xy$, mà $(4x-y)(x+2y)$ chia hết cho 9 nên $A$ chia hết cho 9.

Ví dụ 2. Cho hai số nguyên $a, b$ thỏa $(17a+5b)(5a+17b)$ chia hết cho 11.

Chứng minh rằng $(17a+5b)(5a+17b)$ chia hết cho 121.

Lời giải
  • $(17a+5b)(5a+17b)$ chia hết cho 11 thì $17a + 5b$ hoặc $5a+17b$ chia hết cho 11.
  • Nếu $17a+5b$ chia hết cho 11, khi đó $5a+17b = 22(a+b)  – (17a+5b)$ chia hết cho 11.
  • Khi đó $(17a+5b)(5a+17b)$ chia hết cho 121.
  • Tương tự cho trường hợp còn lại.

Ví dụ 3. Cho $n$ là số tự nhiên. Chứng minh rằng $3^nn^3+1$ chia hết cho 7 khi và chỉ khi $3^n + n^3$ chia hết cho 7.

Lời giải

Bổ đề. Nếu $n$ không chia hết cho 7 thì $n^6-1$ chia hết cho 7.

Chứng minh bổ đề: Xét số dư.

Chiều thuận. Nếu $3^nn^3+1$ chia hết cho 7 thì $3^n + n^3$ chia hết cho 7.

Ta có $3^nn^3 + 1$ chia hết cho 7, suy ra $n$ không chia hết cho 7.

Khi đó $n^33^n + 1 = n^3(3^n+n^3) + 1 – n^6$, mà $1-n^6$ chia hết cho 7 (Theo bổ đề), suy ra $n^3(3^n+n^3)$ chia hết cho 7.

Mà $(n^3,7)=1$, suy ra $3^n+n^3$ chia hết cho 7.

Chiều đảo. Nếu $3^n+n^3$ chia hết cho 7, chứng minh $3^nn^3+1$ chia hết cho 7.

$3^n+n^3$ chia hết cho 7, suy ra $n$ không chia hết cho 7 và $n^3(3^n+n^3)$ chia hết cho 7.

Mà $n^3(3^n+n^3) = n^33^n + 1 + n^6-1$, trong đó $n^6-1$ chia hết cho 7 ,suy ra $3^nn^3+1$ chia hết cho 7.

Bài tập rèn luyện

Bài 1. Tìm các số $x, y$ để $\overline{2x7y5}$ chia hết cho 25.

Bài 2. Tìm số tự nhiên $n$ để $n^2+3n+1$ chia hết cho $n+1$.

Bài 3. Tìm số tự nhiên $n$ để $\dfrac{3n^2 + n+1}{n+2}$ là số nguyên.

Bài 4. Tìm tất cả các số tự nhiên $n$ để $n^2 + 9n – 2$ chia hết cho 11.

Bài 5. Chứng minh rằng $n^2 + n+2$ không chia hết cho 15 với mọi $n$.

Bài 6. Chứng minh rằng $n^2 + 3n+5$ không chia hết cho 121 với mọi $n$.

Bài 7. Ba số nguyên $a,\,b,\,c$thoả mãn điều kiện $a + b + c$ chia hết cho 3. Chứng minh rằng ${a^2}\left( {b + c} \right) + {b^2}\left( {a + c} \right) + {c^2}\left( {a + b} \right)$ chia hết cho 6.

Bài 8. Chứng minh rằng nếu $4x-y$ chia hết cho 3 thì $4x^2 + 7xy-2y^2$ chia hết cho 9.

Bài 9. Cho các số nguyên $a, b, c$ với $b \neq c$. Chứng minh rằng nếu các phương trình $ax^2 + bx + c = 0$ và $(c-b)x^2 +(c-a)x+a+b = 0$ có nghiệm chung thì $a+b+2c$ chia hết cho 3.

Phương pháp chứng minh chia hết

Leave a reply

 

Bài toán chia hết là bài toán quan trọng trong các bài toán số học sơ cấp, trong chương trình trung học cơ sở các bài toán liên quan đến chia hết xuất hiện nhiều trong các kì thi học sinh giỏi cũng như thi vào 10. Trong loạt bài viết này, tôi xin trình bày những phương pháp chứng minh chia hết, giúp các em ôn tập tốt hơn trong kì thi vào 10.

Phương pháp 1. Biến đổi thành tích.

Để chứng minh $A$ chia hết cho $B$, ta có thể làm như sau:

  • Biến đổi $B = C \cdot D$ với $(C, D)=1$ và chứng minh $A$ chia hết cho $C$ và $D$.
  • Biến đổi $A = M \cdot N$ và $B = C \cdot D$, trong đó $M$ chia hết cho $C$ và $N$ chia hết cho $D$.

Ví dụ 1. Chứng minh rằng

a) Tích hai số chẵn liên tiếp chia hết cho 8.

b) Tích bốn số tự nhiên liên tiếp chia hết cho 24.

Lời giải

a) Gọi hai số chẵn liên tiếp là $2n, 2n+2$.

Ta có $2n(2n+2) = 4n(n+1)$. Do $n,n+1$ là hai số liên tiếp nên chắc chắn có một số chẵn, suy ra $n(n+1)$ chia hết cho 2, mà $4$ chia hết cho 4. Suy ra $4n(n+1)$ chia hết cho 8.

Vậy tích hai số chẵn liên tiếp chia hết cho 8.

b) Tích bốn số tự nhiên liên tiếp là $A = n(n+1)(n+2)(n+3)$, ta chứng minh $A$ chia hết cho 24. Ta có $24 = 3 \times 8$ với $(3,8)=1$, nên ta cần chứng minh $A$ chia hết cho 3 và 8.

Nếu $n$ lẻ thì $n+1, n+3$ là hai số chẵn liên tiếp tích chia hết cho 8, suy ra $A$ chia hết cho 8.

Nếu $n$ chẵn thì $n, n+2$ là hai số chẵn liên tiếp, tích chia hết cho 8, suy ra $A$ chia hết cho 8.

Trong ba số  liên tiếp $n, n+1, n+2$ có ít nhất một số chia hết cho 3 nên $A$ chia hết cho 3.

$A$ chia hết cho 3, 8 và $(3,8)=1$, do đó $A$ chia hết cho 24.

Ví dụ 2.  Chứng minh rằng với mọi số tự nhiên $m$ lẻ thì $m^3 + 3m^2 – m – 3$ chia hết cho $48$.

Lời giải

Đặt $A = m^3+3m^2-m-3$, ta có $A = (m+3)(m^2-1)$.

Do $m$ lẻ nên $m = 2n + 1$, $n$ là số tự nhiên. Khi đó $A = (2n+4)((2n+1)^2-1) = 8n(n+1)(n+2)$.

Ta có $n(n+1)(n+2)$ là tích 3 số tự nhiên liên tiếp nên chia hết cho 2 và 3, do đó chia hết cho 6.

Vậy $A$ chia hết cho 48.

Ví dụ 3.  Cho $n$ là số tự nhiên thỏa $n = \dfrac{x^2-1}{2} = \dfrac{y^2-1}{3}$ với $x, y$ là các số nguyên.
a) Chứng minh $n = y^2 – x^2$.
b) Chứng minh $n$ chia hết cho 20.

Lời giải

a) $n = \dfrac{x^2-1}{2} = \dfrac{y^2-1}{3} = \dfrac{y^2-1-(x^2-1)}{3-2} = y^2-x^2$.

b) Ta chứng minh $n$ chia hết cho 4 và 5.

Ta có $n = \dfrac{x^2-1}{2}$, suy ra $x$ lẻ, $x = 2k+1$, khi đó $n = \dfrac{(2k+1)^2-1}{2} = 2k(k+1)$ chia hết cho 4.

Ta có $n = \dfrac{x^2+y^2-2}{5}$, suy ra $x^2+ y^2$ chia 5 dư 2. (1)

Mà $x^2, y^2 \equiv 0, 1, 4 (\mod 5)$.

Do đó (1) chỉ xảy ra khi $x^2 \equiv y^2 equiv 1 (\mod 5)$, suy ra $n=x^2 – y^2$ chia hết cho 5.

Vậy $n$ chia hết cho 20.

Bài tập rèn luyện

Bài 1. Chứng minh rằng hiệu các bình phương của hai số lẻ liên tiếp thì chia hết cho $8$.
Bài 2. Chứng minh rằng nếu $n$ là số chẵn thì $n^2 + 2n$ chia hết cho $8$.
Bài 3. Chứng minh rằng nếu $n$ là số lẻ thì $n^2 – 1$ chia hết cho $8$.
Bài 4. Chứng minh rằng với mọi số tự nhiên $n$ thì $n^4 + 6n^3 + 11n^2 + 6n$ chia hết cho $24$.
Bài 5. Chứng minh rằng nếu $n$ không chia hết cho $3$ thì $n^2 – 1$ chia hết cho $3$.
Bài 6. Chứng minh rằng với mọi số tự nhiên $n$ thì $n^5 – n$ chia hết cho $30$.
Bài 7. Chứng minh rằng nếu $p$ là số nguyên tố lẻ lớn hơn $3$ thì $p^2 – 1$ chia hết cho $24$.
Bài 8. Chứng minhg rằng với mọi số tự nhiên $n$ lẻ thì $n^{12} – n^8-n^4+1$ chia hết cho $512$.
Bài 9. Chứng minh rằng với mọi số $n$ chẵn thì $n^4-4n^3-4n^2+16n$ chia hết cho $384$.
Bài 10. Cho $12$ số tự nhiên có tổng chia hết cho $6$.

Chứng minh rằng tổng lập phương của $12$ số đó cũng chia hết cho $6$.

Đồng dư

Leave a reply

Định nghĩa. Cho hai số nguyên $a,b$ và số tự nhiên $n$. Nếu $a,b$ chia cho $n$ có cùng số dư, ta nói rằng $a$ và $b$ đồng dư khi chia cho $n$ và kí hiệu $ a \equiv b (mod n)$ (đọc là $a$ đồng dư $b$ theo modul $n$).

Nhận xét. $ a \equiv b (mod n) \Leftrightarrow (a-b) \vdots n $

Ví dụ 1. $ 28 \equiv 3(mod5) $

Định lý. Cho $a, b, c$ là các số nguyên, $n$ là số nguyên dương.
1) Nếu $ a\equiv b(mod n), b \equiv c(mod n) $ thì $ a \equiv c(mod n) $
2) Nếu $ a\ \equiv b(mod n)$ thì $ a\pm c \equiv b\pm c(mod n) $ với mọi số nguyên c.
3) Nếu $ a\equiv b(mod n), c \equiv d(mod n) $ thì $a+c \equiv b+d(mod n)$
4) Nếu $ a\equiv b(mod n)$ thì $ c.a\equiv c.b(mod n) $ với mọi số nguyên c.
5) $ a\equiv b(mod n) $ thì $ a^k\equiv b^k(mod n) $ với mọi số nguyên dương k. Đặc biệt nếu $ a\equiv 1(mod n) $ thì $ a^k \equiv 1(mod n) $

Chứng minh
1) Ta có $ a-c=a-b+b-c $, mà $ a\equiv b(mod n), b\equiv c(mod n) $ nên $ a-b\vdots n, b-c\vdots n $, do đó $ a-c \vdots n $ hay $ a\equiv c(mod n) $.
2) $ a-b=(a\pm c)-(b\pm c) $, do đó $ a\equiv b(mod n) \Leftrightarrow a\pm c \equiv b\pm c(mod n) $
3) $ a+c-(b+d)=(a-b)+(c-d)\vdots n $, suy ra $ a+c\equiv b+d(mod n) $
4) Do $ a\equiv b(mod n) $ nên $ a-b\vdots n\Rightarrow ca-cb\vdots n$với mọi số nguyên c. Do đó $ ca\equiv cb(mod n) $.
5) Ta có $ (a^k-b^k)\vdots (a-b) $ với mọi số tự nhiên k. Do đó nếu $ a\equiv b (mod n) $ thì $ a^k\equiv b^k(mod n) $

Ví dụ 2. Chứng minh rằng với mọi số tự nhiên n thì $ 6^{2n}+2^{3n+2}+4 $ chia hết 7.

 

Ta có $ 6\equiv-1(mod 7) $, suy ra $ 6^{2n}\equiv (-1)^{2n}(mod n)\equiv 1(mod n) $
Và $ 2^{3n+1}=2.8^n\equiv 1(\mod 7) $ nên $ 2^{3n+1}\equiv 2(mod 7) $
Do đó $ 6^{2n}+2^{3n+1}+4\equiv2+1+4\equiv0(mod 7) $ hay $ 6^{2n}+2^{3n+1}+4\vdots7 $.

Định lý 27. Cho a, b là các số nguyên, $ m_1, m_2 $ là các số tự nhiên thỏa $ a\equiv b(mod m_1), a\equiv b\ (mod m_2) $ và $ (m_1, m_2)=1 $ thì $ a\equiv b(mod m_1\cdot m_2) $.

Chứng minh. Ta có $ m_1|(a-b) $ và ($ m_1, m_2 $)=1 thì $ m_1.m_2|(a-b) $. Từ đó suy ra điều cần chứng minh.\

Bài tập rèn luyện

Bài 1. Cho $n$ là số tự nhiên. Tìm chữ số tận cùng của các số $ 2^n, 3^n, 4^n $.

Bài 2. Chứng minh rằng $ 1941^{1963}+ 1963^{1941}-1 $ chia hết cho 7.

Bài 3. Chứng minh $ 3^{n+2}+4^{2n+1} $ chia hết cho 13.

Bài 4. Tìm phần dư của $ 1! + 2!+…+10! $ khi chia hết cho 15.

trong đó $ n!= 1.2…(n-1)n. $

Bài 5. Tìm số nguyên dương nhỏ nhất m biết $ m \equiv 2\ (mod\ 6),\ m \equiv 2\ (mod\ 8) $

Bài 6. Chứng minh $ 2^{2^n} +5 $ là hợp số.

Bài 7. Cho $ a^2+b^2 \equiv 0\ (mod\ 3) $, chứng minh $ a \equiv 0\ (mod\ 3),\ b \equiv 0\ (mod\ 3) $.

Bài 8. Tìm hai chữ số tận cùng của số $ 9^{9^9} $.

Bài 9. Một lớp học khi sắp thành 2 hàng, 3 hàng, 5 hàng đều dư ra 1 em. Hỏi lớp học đó có bao nhiêu học sinh biết rằng số học sinh không nhiều hơn 50.

Bài 10. Chứng minh rằng nếu $ a_i \equiv b_i (mod\ m) $ với i = 1, 2, …,n thì

a) $$  \qquad \sum_{i=1}^{n} a_{i}\equiv\sum_{i=1}^{n} b_{i} \quad \text{(mod m)}$$

b) $$ \qquad \prod_{i=1}^{n} a_{i}\equiv \prod_{i=1}^{n} b_{i} \quad \text{(mod m)}$$

Trong đó $$ \qquad \sum_{i=1}^{n} {x_i} = x_1+x_2+…+x_n,\qquad \prod_{i=1}^{n} x_{i}=x_1, x_2…x_n $$.

Số nguyên tố – Hợp số

Leave a reply

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 $

Quy tắc cộng – Quy tắc nhân

Leave a reply

Quy tắc cộng – Quy tắc nhân

 

Quy tắc cộng. Để thực hiện một công việc có thể sử một trong $k$ phương án $A_1, A_2, …, A_k$. Nếu phương án $A_1$ có $a_1$ cách thực hiện, $A_2$ có $a_2$ cách thực hiện…$A_k$ có $a_k$ cách thực hiện. Khi đó số cách thực hiện công việc là: $a_1 + a_2 + …+ a_k$.

Quy tắc cộng. (Dạng khác) Tập $A_1$ có $a_1$ phần tử, $A_2$ có $a_2$ phần tử, …, $A_k$ có $a_k$ phần tử, $A_i \cap A_j = \emptyset \forall i, j = 1, 2, …, k, i \neq j$. Khi đó số phần tử của tập ${A_1} \cup {A_2} \cup … \cup {A_k}$ là $a_1 + a_2 + …+ a_k$.

Nguyên lý bù trừ. Cho hai tập hợp A và B. Khi đó [|A \cup B| = |A| + |B| – |A \cap B| ]
Khi $A \subset X$ thì $|\overline{A}| = |X| – |A|$.

Quy tắc nhân. Để thực hiện một công việc, ta cần thực hiện lần lượt qua các giai đoạn $A_1, A_2, …, A_k$. Nếu $A_1$ có $a_1$ cách thực hiện, $A_2$ có $a_2$ cách thực hiện, …, $A_k$ có $a_k$ cách thực hiện. Khi đó số cách thực hiện công việc là $a_1 \times a_2 \times …\times a_k$.

Quy tắc nhân (Dạng khác) Cho tập $A_1$ có $a_1$ phần tử, $A_2$ có $a_2$ phần tử, …, $A_k$ có $a_k$ phần tử. Khi đó số phần tử của tích Decarters $A_1 \times A_2 \times … \times A_k = {(x_1, x_2, …x_k)| x_i \in A_i \forall i = 1, 2, …, k }$ là $a_1 \times a_2 \times a_3 \times … \times a_k$.

Các ví dụ

Ví dụ 1. Cho tập $A = {0, 1, 2, 3, 4, 5, 6}$. Từ tập $A$ có thể lập được bao nhiêu số tự nhiên

a) Có 5 chữ số khác nhau.
b) Không lớn hơn 4000.
c) Có bao nhiêu số lẻ có các chữ số khác nhau.
d) Có bao nhiêu số có 4 chữ số, mà các chữ số không nhất thiết phải khác nhau.
e) Có bao nhiêu số có 5 chữ số không có số 1 hoặc không có số 2.

Ví dụ 2.  Có thể tạo ra được bao nhiêu hình vuông từ bảng các điểm đã cho như hình sau ($8 \times 8$). Biết rằng:

a) Cạnh hình vuông song song với cạnh hình vuông lớn.
b) Bất kì.

Ví dụ 3.  Cho $n$ có phân tích thành thừa số nguyên tố như sau $$n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$
Tính số ước nguyên dương của $n$.

Ví dụ 4. bao nhiêu số tự nhiên không lớn hơn 1000

a) Có ít nhất một chữ số 1. (\textbf{272})
b) Không chia hết cho 2 hoặc 3 hoặc 5.

Bài tập rèn luyện

Bài 1. Đội tình nguyện viên của trường PTNK gồm 6 bạn lớp 10, 3 bạn lớp 11 và 5 bạn lớp 12. Cần chọn ra 3 bạn làm ban chỉ huy trong đó có 1 đội trưởng, một đội phó và 1 ủy viên. Hỏi có bao nhiêu cách chọn thỏa:

a) Chọn tùy ý.
b) Bạn tổ trưởng lớp 11.

Bài 2. Thầy dạy toán có một số bài tập gồm: 6 bài toán khó, 5 bài toán trung bình và 7 bài toán dễ và 4 bài siêu dễ. Thầy muốn lập một đề thi gồm 1 câu hỏi khó, 1 câu hỏi trung bình, 1 câu hỏi dễ và 1 câu siêu dễ. Hỏi có bao nhiêu cách chọn bài.

Bài 3.
a) Có bao nhiêu dãy nhị phân có độ dài $n$.
b) Có bao nhiêu tập con của tập có $n$ phần tử.

Bài 4. Có bao nhiêu số nguyên dương có 5 chữ số:

a) Có các chữ số chẵn lẻ xen kẽ.
b) Có chữ số 1 và 2 nhưng không đứng cạnh nhau.
c) Có các chữ số khác nhau và có chữ số 1.
d) Có 4 chữ số không có chữ số 1 hoặc không có chữ số 0.
e) Số chẵn có 5 chữ số khác nhau và chữ số 3 và 0 không đồng thời có mặt.
f) Có 5 chữ số có chữ số 1 hoặc có chữ số 2.
Bài 5.  Cho $A = {1, 2, 3, 4, 5, 6, 7}$ và $B = {a, b, c}$. Có bao nhiêu ánh xạ $f$ từ $A$ vào $B$.

Bài 6. Có bao nhiêu cặp số $(a,b)$ mà bội chung nhỏ nhất của $a, b$ là $2017^3 2018^5 2019^4$

Bài 7. Lớp 10 Toán có 6 bạn nữ và 6 bạn nam được xếp ngồi trên hai dãy ghế đối diện nhau, mỗi dãy có 6 ghế. Có bao nhiêu cách xếp thỏa:

a) Xếp bất kì.
b) Mỗi bạn nam ngồi đối diện với một bạn nữ.

Bài 8. Có 5 bạn vào rạp xem phim, trong rạp chỉ còn một dãy ghế gồm 8 ghế. Hỏi có bao nhiêu cách để các bạn ngồi, biết rằng mỗi người đều được ngồi vị trí bất kì.

Bài 9. Cho tập $A = {1, 2, 3,4,5,6}$. Có bao nhiêu số mà các chữ số thuộc $A$ thỏa:

a) Số chẵn có 5 chữ số khác nhau.
b) Số có 3 chữ số khác nhau và chia hết cho 9. (Số chia hết cho 9 khi và chỉ khi tổng các số chia hết cho 9)
c) Số có 4 chữ số khác nhau và chia hết cho 25.
d) Số có 5 chữ số có dạng $\overline{abcba}$ ($a, b,c$ đôi một khác nhau).
e) Số có 6 chữ số có dạng$\overline{12abab}$ và chia hết cho 5.

Bài giảng quy tắc cộng – Quy tắc nhân.

 

Tập san Star Education – Số 3 năm 2019

Leave a reply

Tập san Star Education là tập hợp các chuyên đề bài viết về toán do các giáo viên của Star Education biên soạn, ngoài ra còn có sự hợp tác của giáo viên học sinh khác nhằm đem đến cho bạn đọc một nguồn tài liệu mới tham khảo.

Tập san ra định kì mỗi năm hai số, tháng 11 và tháng 05.

tap san STAR 03-2019