Category Archives: Chuyên đề

Phương trình nghiệm nguyên – P3

Leave a reply

Ta tiếp tục với phương pháp giải phương trình nghiệm nguyên, nay ta sẽ bàn tới phương pháp sử dụng đồng dư, chú ý một số cách tiếp cận sau:

  • Sử dụng đồng dư để chứng minh phương trình vô nghiệm.
  • Sử dụng đồng dư để suy ra tính chất của biến (tính chẵn lẻ, …), đưa về các dạng đã biết.

Ví dụ 1.  Giải phương trình $ x^3 +21y^3+5=0 $.

Lời giải
  • Ta có với mọi $x$ thì
    $ x^3\equiv 0, 1, -1\ (\mod 7) \Rightarrow x^3 +21y^2+5\equiv 5,6,4\ (\mod 7) $
  • Do đó phương trình vô nghiệm.

Ví dụ 2. Giải phương trình trong tập số tự nhiên: $6^x = y^2+y-2 $.

Lời giải
  • Với mọi số nguyên x thì $ 6^x \equiv 1\ (mod\ 5) $.
  • Mặt khác, $ y^2+y-2 = (y-1)(y+2) \equiv 0,3,4\ (mod\ 5) \Rightarrow $ phương trình vô nghiệm.

Ví dụ 3. Tìm nghiệm nguyên dương của phương trình $$7^x – 9^y = 4$$

Lời giải
  • Ta có $9^y \equiv 1 (\mod 4)$ suy ra $7^x \equiv 2 (\mod 4)$ suy ra $x$ chẵn. $x = 2k$.
  • Ta có $7^{2k} – 3^{2y} = 4 \Leftrightarrow (7^k-2)(7^k+2) = 3^{2y}$.
  • Dễ thấy $(7^k-2, 7^k+2) = 1$ suy ra $7^k-2 = 1, 7^k+2 = 3^{2y}$ vô nghiệm.

Ví dụ 4. Tìm $x, y, z$ nguyên dương và $z \geq 2$ thỏa $3^x + 5^x = y^z$.

Lời giải
  • Nếu $x = 1$ ta có $y^z = 8$ thì $y = 2, z=3$.
  • Nếu $x$ chẵn. $3^x + 5^x \equiv 2( \mod 4)$, suy ra $y$ chẵn và $y^z \equiv 2(\mod 4)$, suy ra $z = 1$. (vô lý).
  • Nếu $x$ lẻ, $x > 1$. Khi đó $LHS=3^x + 5^x = (3+5)(3^{x-1}-3^{x-2}\cdot 5 +\cdots +5^{x-1})$.
  • Ta có $3^{x-1}-3^{x-2}\cdot 5 +\cdots +5^{x-1}$ có $x$ số hạng lẻ, nên tổng là lẻ. Do đó $LHS$ chia hết cho 8, nhưng ko chia hết cho 16, kết hợp $z > 1$ ta được $z=3$.
  • $3^x + 5^x = y^3$. $5^6 \equiv 1 (\mod 9)$, suy ra $5^x \equiv 5 (\mod 9)$ nếu $x \equiv 1 (\mod 6)$; $5^x \equiv -1 (\mod 9)$ khi $x \equiv 3 (\mod 6)$; $5^x \equiv 7 (\mod 9)$ khi $x \equiv 5(\mod 6)$.
  • Mặt khác $y^3 \equiv 0, 1, -1 (\mod 9)$. Do đó $x \equiv 3 (\mod 6)$.
  • Lại có $3^x + 5^x \equiv 5 (\mod 7)$ khi $x \equiv 3 (\mod 6)$.
    Do đó phương trình vô nghiệm.
  • Kết luận $(1,2,3)$.

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

Bài 1. Tìm nghiệm nguyên của các phương trình sau:
a) $2^x-3^y=1$;

b) $2^x-3^y=7$;
c) $2^x+3^y=z^2$;
d) $3^x+4^y=5^z$;
e) $3^x+4^y=7^z$.
Bài 2. (PTNK 2013) Cho $M = a^2 + 3a + 1$ với $a$ là số nguyên dương.
a)  Chứng minh rằng mọi ước của $M$ đều là số lẻ.
b) Tìm $a$ sao cho $M$ chia hết cho 5. Với những giá trị nào của $a$ thì $M$ là lũy thừa của 5?
Bài 3. (PTNK 2009)
a) Chứng minh rằng không tồn tại số tự nhiên $a$ sao cho ${a^2} + a = {2010^{2009}}$
b) Chứng minh rằng không tồn tại số tự nhiên $a$ sao cho $a + {a^2} + {a^3} = {2009^{2010}}$

Phương pháp chứng minh quy nạp – Các dạng khác

Leave a reply

Trong bài này, chúng ta tiếp tục tìm hiểu thêm và phương pháp quy nạp. Ngoài dạng quy nạp như đã biết ta còn một số dạng quy nạp khác như: Quy nạp mạnh, quy nạp bước nhảy, quy nạp lùi.

Quy nạp mạnh được phát biểu như sau: Để chứng minh mệnh đề $P(n)$ đúng với mọi số tự nhiên $n$, ta thực hiện theo hai bước sau:

  • Chứng minh $P(n)$ đúng với $n=1$.
  • Giả sử $P(n)$ đúng với $1, 2, \cdots, n$. Chứng minh $P(n+1)$ đúng.

Ví dụ 1. Cho $x$ thỏa $x+\dfrac{1}{x}$ là số nguyên. Chứng minh rằng $x^n+\dfrac{1}{x^n}$ là số nguyên với mọi $n$.

Lời giải. 

  • Ta có $x + \dfrac{1}{x}$ là số nguyên  đúng (theo giả thiết).
  • Giả sử $x^k + \dfrac{1}{x^k}$ là số nguyên với mọi $k = \overline{1,n}$. Ta cần chứng minh $x^{n+1} + \dfrac{1}{x^{n+1}}$.
    • $(x^{n+1} + \dfrac{1}{x^{n+1}} = (x+\dfrac{1}{x})(x^n + \dfrac{1}{n})  – (x^{n-1}+\dfrac{1}{x^{n-1}})$.
    • Theo giả thiết quy nạp thì $x^{n+1} + \dfrac{1}{x^{n+1}}$ là số nguyên.
  • Vậy ta có $x^n + \dfrac{1}{x^n}$ là số nguyên với mọi $n$.

 

Dạng kế tiếp là Quy nạp bước nhảy  được phát biểu như sau: Chứng minh mệnh đề $P(n)$ đúng với mọi $n$, ta làm như sau:

  • Chứng minh $P(1), P(2), \cdots, P(k)$ đúng.
  • Giả sử $P(n)$ đúng. Ta chứng minh $P(n+k)$ đúng.

Ví dụ 2. Chứng minh rằng với mọi số tự nhiên $M$ tồn tại số tự nhiên $n$ và cách chọn các dấu $+$ hoặc $-$ sao cho

$M = \pm 1^2 \pm 2^2 \cdots \pm n^2$.

Lời giải.

  • Khi $M = 1, 2, 3, 4$ ta có $1 = 1^2$, $2 = -1^2-2^2-3^2+4^2$, $3 = -1^2+2^2$ và $4 = 1^2-2^2-3^2+4^2$.
  • Giả sử đúng với $M$, tức là tồn tại $n$ thỏa $M = \pm 1^2 \pm 2^2 \cdots \pm n^2$, khi đó $M + 4 = \pm 1^2 \pm 2^2 \cdots \pm n^2 +(n+1)^2-(n+2)^2-(n+3)^2 + (n+4)^2$.

Ví dụ 3.  Chứng minh rằng với mọi số tự nhiên $n$ thì phương trình $a^2 + b^2 = c^n$ luôn có nghiệm trong tập các số nguyên dương.

Lời giải. 

  • Rõ ràng nếu $n=1, 2$ thì phương trình luông có nghiệm nguyên dương.
  • Giả sử phương trình có nghiệm nguyên dương là $a, b, c$ với $n$ nào đó, tức là $a^2 + b^2 = c^n$.
    • Khi đó với $n+2$ thì xét $(ac), (bc), c$: $(ac)^2+(bc)^2 = c^2 (a^2+b^2) = c^{n+2}$.
    • $(ac, bc, c$ là nghiệm.
  • Vậy phương trình luôn có nghiệm với mọi $n$.

Dạng kế tiếp là Quy nạp lùi được phát biểu như sau:

  • Chứng minh $P(a_i)$ đúng với dãy $(a_i)$ là dãy con tăng thực sự của tập các số tự nhiên.
  • Giả sử $P(n)$ đúng, chứng minh $P(n-1)$ đúng.

Ví dụ 4. 

a) Hãy chỉ ra cách sắp 8 số nguyên dương đầu tiên 1, 2, …, 8 thành một dãy $a_1, a_2 ,…, a_8$ sao cho 2 số $a_i, a_j$ bất kì $(i < j)$ thì mọi số trong dãy nằm giữa $a_i$ và $a_j$ đều khác $\dfrac{a_i + a_j}{2}$.
b) Chứng minh rằng với $N$ số nguyên dương đầu tiên $1, 2, …, N$ luôn tìm được cách sắp thành dãy $a_1, a_2, …, a_N$ sao cho dãy thỏa mãn điều kiện như câu a).
Lời giải.

a) Một cách xếp thỏa đề bài là 26481537.\
b)

Bước 1.Ta chứng minh bằng quy nạp với $n = 2^k$ thì luôn tồn tại một cách xếp thỏa đề bài.

  • Nếu $k = 1$, hiển nhiên đúng.
    Giả sử luôn tồn tại một cách xếp thỏa đề bài với $n = 2^k$, cách xếp đó là $a_1, a_2, …, a_n$.
    Ta chứng minh tồn tại một cách xếp với $n = 2^{k+1}$.
    Thật vậy xét hoán vị $(2a_1, 2a_2,…, 2a_n, 2a_1-1, 2a_2-1, …, 2a_n-1)$ là một hoán vị của $1, 2, …, 2^{k+1}$. Ta chứng minh hoán vị trên thỏa đề bài.

    • Ta có nếu $a_i, a_j \in \{2a_1, 2a_2, …, 2a_n\}$ theo giả thiết quy nạp không có số nào nằm giữa $a_i, a_j$ bằng $\dfrac{1}{2}(a_i+a_j)$.
    • Nếu $a_i \in \{2a_1, …, 2a_n\}, a_j \in \{2a_1-1, 2a_2-1, …, 2a_n-1\}$ thì $\dfrac{1}{2}(a_i +a_j)$ không phải số nguyên.
    • Nếu $a_i, a_j \in \{2a_1-1, 2a_2-1, …, 2a_n-1\}$ theo giả thiết quy nạp thì cũng có số nào nằm giữa $a_i, a_j$ bằng $\dfrac{1}{2}(a_i + a_j)$.

Vậy bài toán đúng với $n = 2^k$.(1)
Bước 2. Nếu bài toán đúng với $n$, ta chứng minh bài toán đúng với $n-1$.

Xét các số $a_1, a_2, …, a_n$ là một hoán vị thỏa đề bài của $1,2,…,n$.

Khi đó nếu xóa bất kì số nào trong các số $a_1, …, a_n$ thì dãy còn lại vẫn thỏa điều kiện. (2)
Từ (1) và (2) ta có điều cần chứng minh.

Quy nạp lùi cũng là một trong những cách chứng minh bất đẳng thức Cauchy tổng quát: $\dfrac{a_1+a_2 + \cdots+a_n}{n} \geq \sqrt[n]{a_1a_2\cdots a_n}$.

Các bạn tự làm thử nhé.

Trên đây là một số dạng quy nạp thường gặp trong chứng minh toán. Tùy theo tình huống mà ta sử dụng cho phù hợp, các bạn cần làm thêm nhiều bài tập để rèn luyện.

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

Bài 1. Ta gọi tổng các số tự nhiên từ 1 đến n là số tam giác. Chứng minh rằng tồn tại vô hạn các số tam giác đồng thời là số chính phương.

Bài 2. (Chọn đội tuyển PTNK 2014)Tìm số nguyên dương $n$ lớn nhất thỏa mãn các điều kiện sau:

  • $n$ không chia hết cho 3;
  • Bảng vuông $n \times n$ ô không thể được phủ kín bằng 1 quân tetramino $1 \times 4$ và các quân trimino kích thước $1 \times 3$. Trong phép phủ các quân tetramino và trimino được phép quay dọc nhưng không được phép chườm lên nhau hoặc nằm ngoài ra bảng vuông.

Bài 3. Có $n$ số tự nhiên từ 1 đến $n$ được viết thành một dòng theo một thứ tự nào đó. Mỗi bước thực hiện biến đổi như sau: nếu số đầu tiên là $k$ thì $k$ số đầu tiên sẽ được viết theo thứ tự ngược lại. Chứng minh rằng sau hữu hạn bước thì số đầu tiên của dòng là số 1.

Bài 4. Trong cuộc họp có $2n$ ($n \geq 2$) người, một số người bắt tay nhau và người ta đếm được có $n^2+1$ cái bắt tay. Chứng minh rằng có $n$ bộ ba, mà mỗi bộ ba đôi một bắt tay nhau.

Bài 5. Chứng minh rằng với mọi số tự nhiên $n$ tồn tại các số nguyên $x, y, z$ phân biệt sao cho $x^2+y^2+z^2 = 14^n$.

Bài 6. Trong một giải đấu tennis có 10 người tham dự, hai đối thủ gặp nhau đúng một trận. Chứng minh rằng, sau khi kết thúc giải có thể sắp xếp các tay vợt thành một hàng mà người đứng trước thắng người đứng sau.

Phương pháp chứng minh quy nạp – P2

Leave a reply

Trong phần trước ta đã làm quen với phương pháp chứng minh quy nạp và áp dụng vào chứng minh một vài đẳng thức, bất đẳng thức hay các bài toán chia hết. Bài này tiếp tục là ứng dụng của quy nạp trong việc chứng minh các bài toán khác, trong cái đề thi học sinh giỏi hay tuyển sinh.

Ví dụ 1. Người ta lát nền nhà hình vuông kích thước $n \times n$ ô bằng các viên gạch như hình vẽ dưới sao cho còn chừa lại một ô không lát.
a) Hãy chỉ ra một cách lát như trên với nền nhà kích thước $4 \times 4$ và $8 \times 8$.
b) Hãy chứng minh rằng luôn tồn tại một cách lát nền nhà có kích thước $2^k \times 2^k$ (k nguyên dương) với ô trống còn lại nằm ở vị trí $(i,j)$ bất kì.

Lời giải

a) Các bạn tự làm.
b) Ta chứng minh bằng quy nạp.

  • Với $k = 2$ hiển nhiên đúng.
  • Giả sử với $k$ thì nền $2^k \times 2^k$ bỏ ô $(i;j)$ bất kì thì luôn phủ được. Ta chứng minh đúng với $k+1$.
    Với nền nhà $2^{k+1} \times 2^{k+1}$ ta chia thành 4 hình vuông $2^k \times 2^k$. Khi đó ô bỏ đi thuộc một trong 4 hình vuông đó, ta phủ được hình vuông này theo giả thiết quy nạp. Tiếp tục,theo giả thiết quy nạp, với 3 hình vuông còn lại, bỏ đi ô ở góc (hình vẽ) thì ta có thể phủ được. Khi đó 3 ô ở góc ta phủ tiếp bằng một viên gạch.
  • Với cách thực hiện đó thì ta có thể phủ được nền nhà $2^{k+1} \times 2^{k+1}$ khi bỏ ô bất kì.

Ví dụ 2. Trong cuộc họp có $2n$ ($n \geq 2$) người, một số người bắt tay nhau và người ta đếm được có $n^2+1$ cái bắt tay. Chứng minh rằng có 3 người đôi một bắt tay nhau.

Lời giải
  • Rõ ràng bài toán đúng khi $n=2$.
  • Giả sử bài toán đúng với $n$, ta chứng minh bài toán đúng với $n+1$. Xét hai người $A, B$ bắt tay.
    Nếu số bắt tay của $A$ và $B$ với $2n$ người còn lại không vượt quá $2n$ thì $n$ người kia có $n^2+1$ cái bắt tay, ta có điều cần chứng minh.
    Nếu số người bắt tay với $A, B$ là hơn $2n$ cái.
  • Do đó trong $2n$ người kia thì sẽ có ít nhất một người bắt tay với cả $A$ và $B$, ta có điều cần chứng minh.

Ví dụ 3.  a) Cho bốn số nguyên dương $a_1, a_2, a_3, a_4$ sao cho $1 \leq a_k \leq k$ với mọi $ k= 1,2, 3, 4$ và tổng $S = a_1 + a_2 + a_3 + a_4$ là một số chẵn. Chứng minh rằng có ít nhất một trong các số dạng $\pm a_1 \pm a_2 \pm a_3 \pm a_4$ có giá trị bằng 0.
b) Cho 1000 số nguyên dương $a_1, a_2,…, a_{1000}$ sao cho $1 \leq a_k \leq k$ với $k = 1, 2, …, 1000$ và tổng $S = a_1 + a_2 + …+a_{1000}$ là một số chẵn.\
Hỏi trong các số có dạng $\pm a_1 \pm a_2 … \pm a_{1000}$ có số nào bằng 0 hay không? Giải thích vì sao?

Lời giải

a) Ta có $4 \leq S \leq 10$ và $S$ chẵn, suy ra $S = 4, 6, 8, 10$. Xét các trường hợp sau:

  • $S = 4$, suy ra $a_1 = a_2 = a_3 = a_4 = 1$. Suy ra $- 1 – 1+ 1 + 1 = 0$.
  • $S = 6$ ta có $6 = 1 + 1 + 1 + 3 = 1 + 1 + 2 + 2$, suy ra có một cách thỏa đề bài.
  • $S = 8$ ta có $8 = 1 + 1 + 2 + 4 = 1 + 1 + 3 + 3 = 1 + 2 + 2 + 3 = 2 + 2 + 2 + 2$. Suy ra mỗi cách đều tồn tại một cách chọn dấu $ + , – $ thỏa đề bài.
  • $S = 10 = 1 + 2 + 3 + 4$. Suy ra có một cách thỏa đề bài.

a) Ta chứng minh bằng quy nạp mệnh đề sau: Cho $n$ các số nguyên dương thỏa $1 \leq a_k \leq k$ thỏa $S_n = a_1 + …+a_n$ chẵn. Khi đó tồn tại số có dạng $\pm a_1 \pm a_2 … \pm a_{n}$ bằng 0.

  • Khi $n = 2$ ta có $a_1 + a_2$ chẵn, suy ra $a_1 = a_2 = 1$. Suy ra $a_1 – a_2 = 0$.
  • Giả sử bài toán đúng với $k\leq n$. Ta chứng minh bài toán đúng với $n + 1$. Ta có $S_{n+1} = a_1 + …+a_{n} + a_{n+1}$ chẵn. Ta có $0\leq |a_{n} – a_{n+1}| \leq n$.
    • Nếu $a_n – a_{n+1} = 0$ ta áp dụng giả thiết quy nạp với $n-1$ số $a_1, …, a_{n-1}$ ta có điều cần chứng minh.
    • Nếu $a_n – a_{n+1} \neq 0$. Áp dụng giả thiết quy nạp với $n$ số $a_1, a_2, …, a_{n-1}, |a_n-a_{n+1}|$ ta thấy $a_1 + …+a_{n+1}$ chẵn nên $a_1 + …+a_{n-1} + |a_n – a_{n+1}|$ chẵn.
    • Suy ra tồn tại số có dạng $\pm a_1 \pm a_2 … \pm |a_{n}-a_{n+1}| = \pm a_1 \pm a_2 … \pm a_{n+1}$ bằng 0.

 

Ví dụ 4. (USAMO 2002) Cho tập S có 2002 phần tử, số tự nhiên $k$ thỏa $0 \leq k \leq 2^{2002}$ chứng minh rằng tồn tại cách tô màu các tập con của S bằng hai màu xanh và đỏ thỏa:
a)  Có đúng $k$ tập được tô màu đỏ.
b) Hợp của hai tập đỏ là một tập đỏ.
c) Hợp của hai tập xanh là một tập xanh.

Lời giải
  • Ta chứng minh bài toán đúng với tập $S$ có số phần tử $n$ bất kì bằng quy nạp.

    Rõ ràng bài toán đúng với $n=1$, $S=\{1\}$. Nếu $k=0$ tô màu xanh cả hai tập con. Nếu $k=1$ tô màu đỏ tập $S$, xanh tập rỗng. Nếu $k=2$ thì tô $S$ và rỗng đều màu đỏ.

  • Giả sử $S$ có $n$ phần tử thì với mọi $k$ đều tồn tại cách tô thỏa đề bài.
    Ta chứng minh bài toán đúng với $S$ có $n+1$ phần tử.
    Giả sử $S = \{1, 2, \cdots, n, n+1\}$, $0 \leq k \leq 2^{n+1}$.

    • Nếu $k \leq 2^n$.Theo giả thiết quy nạp các tập con của $\{1, 2, \cdots, n\}$ được tô thỏa đề bài và các tập con chứa $n+1$ ta tô màu xanh. Rõ ràng cách tô này thỏa đề bài.
    • Nếu $ 2^n < k \leq 2^{n+1}$. Thì ta chỉ cần đổi màu các tập tô như trường hợp trên, tập nào tô màu xanh thì đổi thì màu đỏ và ngược lại. Rõ ràng thỏa đề bài.

Trên đây là một vài ví dụ khá hay về áp dụng của Quy nạp, tất nhiên còn nhiều bài tập khác cũng hấp dẫn không kém, các bạn tự tìm hiểu nhé. Chúng ta sẽ trở lại trong bài viết sau về một số dạng quy nạp thường gặp.

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

Bài 1. Lúc đầu có $n$ lít nước để vào một số lu, mỗi lu chứa đúng một số nguyên dương lít nước, ta thực hiện cách đong nước như sau: nếu số nước ở lu $A$ nhỏ hơn hoặc bằng lu $B$ thì ta có thể cho hết nước của $B$ vào $A$ một lượng bằng lượng nước lu $A$ đang có.
a) Nếu có 3 lu nước chứa lần lượt $2, 3, 8$ thì có thể đưa về hai lu không? Tại sao?
b) Nếu $n=1024 $. Chứng minh rằng ta có thể đưa số nước hết về một lu. Giả sử lu này là lu lớn, chứa đủ số nước đã có.
Bài 2. Cho $n$ đội bóng, $n$ là số chẵn lớn hơn 2.  Mỗi một lượt, các đội chia cặp để đấu với nhau một trận. Chứng minh rằng sau hai lượt thì có thể tìm được $\dfrac{n}{2}$ đội mà không có hai đội nào đấu với nhau.

Bài 3. Cho $n = 2^k$, chứng minh rằng người ta có thể chọn $n$ số nguyên từ $2n-1$ số nguyên để tổng của chúng chia hết cho $n$.

Bài 4. Gọi $x_1, x_2$ là nghiệm của phương trình $x^2 + 2017 x – 1 = 0$. Đặt $S_n = x_1^2+x_2^n$. Chứng minh rằng $S_n$ và $S_{n+1}$ là nguyên tố cùng nhau với mọi $n$.

Phương pháp chứng minh quy nạp – P1

Leave a reply

Phương pháp chứng minh quy nạp là một trong những phương pháp chứng minh quan trọng trong toán học. Trong bài viết nhỏ này dành cho các bạn THCS chúng tôi xin trình bày một số dạng của phương pháp này trong việc chứng minh các bài toán ở các lĩnh vực như: Đại số, số học, tổ hợp. Hy vọng các em có thể nắm bắt vận dụng phù hợp trong các tình huống cụ thể.

Để chứng minh một mệnh đề $P(n)$ là đúng với mọi số nguyên dương $n$, ta thực hiện các bước sau:

  • Bước cơ sở:      Chứng minh $P(1)$ đúng.
  • Bước quy nạp: Giả sử $P(n)$ đúng với $n$ nào đó (giả thiết quy nạp), chứng minh $P(n+1)$ đúng.

Ví dụ 1. Chứng minh rằng với mọi số nguyên dương $n$ thì $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$.

Lời giải. 

  • Khi $n=1$ rõ ràng : $1 = \dfrac{1(1+1)}{2}$.
  • Giả sử đẳng thức đúng với $n$, ta chứng minh đẳng thức đúng với $n+1$.
    • Thật vậy áp dụng giả thiết quy nạp ta có: $1+2+\cdots+n+n+1 = \dfrac{n(n+1)}{2} + n+1 = \dfrac{(n+1)(n+2)}{2}$.
  • Vậy đẳng thức đúng với mọi $n$.

Ví dụ 2. Chứng minh $n^3+11n$ chia hết cho 6 với mọi số tự nhiên $n$.

Lời giải. 

  • Khi $n = 0$ ta có $0^3+11\cdot 0 = 0$ chia hết cho 6.
  • Giả sử $n^3+11n$ chia hết cho 6, ta chứng minh $(n+1)^3+11(n+1$ chia hết cho 6.
    • Thật vậy $(n+1)^3 + 11(n+1) = n^3 + 11n + 3n(n+1)+12$.
    • Theo giả thiết quy nạp thì $n^3+11n$ chia hết cho 6, và $3n(n+1), 12$ cũng chia hết cho 6 nên $(n+1)^3+11n$ chia hết cho 6.
  • Vậy $n^3+11n$ chia hết cho 6 với mọi $n$.

Trong một số trường hợp ta cần chứng minh $P(n)$ đúng với mọi số tự nhiên $n \geq n_o$ nào đó, ta cũng làm tương tự, chỉ thay bước cơ sở thành: Chứng minh $P(n_o)$ đúng.

Ví dụ 3. Chứng minh rằng $2^n > n^2$ với mọi $n \geq 5$.

Lời giải. 

  • Khi $n = 5$ ta có $2^5 > 5^2 $( đúng)
  • Giả sử $2^n > n^2$ với $n> 5$. Ta cần chứng minh $2^{n+1} > (n+1)^2$.
    • Thật vậy áp dụng giả thiết quy nạp ta có $2^{n+1} = 2\cdot 2^n > 2n^2$.
    • Mà $2n^2 > (n+1)^2 \Leftrightarrow  n^2-2n+1 > 0$ (đúng với $n > 5$).
    • Do đó $2^{n+1} > (n+1)^2$.
  • Vậy $2^n > n^2$ với mọi $n \geq 5$.

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

Bài 1. Chứng minh các đẳng thức sau:

a) $1^2 + 2^2 + …+ n^2 = \dfrac{n(n+1)(2n+1)}{6}.$

b) $1^3 + 2^3 + …+n^3 = \dfrac{n^2(n+1)^2}{4}$.

c) $\dfrac{1}{1.2.3} + \dfrac{1}{2.3.4} + …+ \dfrac{1}{n(n+1)(n+2)} = \dfrac{n(n+3)}{4(n+1)(n+2)}$.

Bài 2.

a) Chứng minh rằng $n! > 3^n$ với mọi $n > 7$.

b) Chứng minh rằng với số thực $a > – 1$, thì với mọi số tự nhiên $n$ ta có $(1+a)^n \geq 1+ na$.

Bài 3. Chứng minh rằng với mọi số tự nhiên $n$ thì:

a) $5^{2n+1}+2^{n+4} + 2^{n+1}$ chia hết cho 23.

b) Với $ n $ là số tự nhiên chẵn, chứng minh rằng: $$ (20^n+16^n-3^n-1)\ \vdots \ 323. $$

Phương trình nghiệm nguyên – P2

Leave a reply

Tương tự như phân tích thành tổng, phương pháp tiếp theo là Biến đổi thành tích. Phương pháp này dựa trên tính chất: Mỗi số nguyên dương được phân tích hữu hạn lần thành tích của hai hay nhiều số khác nhau.

Ví dụ 1. Giải phương trình nghiệm nguyên $$2xy + 3x + 4y = 9$$

Lời giải
  • Ta biến đổi thành $(x+2)(2y+3) = 15$.
  • Do đó $x+2 \in \{-15, -5, -3, -1, 1, 3, 5, 15\}$.
  • Giải ra được các nghiệm $(x;y)$ là: $(-17;-2), (-7;-3), (-5;-4), (-3;-9), (-1;6), \\(1;1), (3;0), (13;-1)$.

Ví dụ 2. Tìm nghiệm tự nhiên của phương trình $(xy-7)^2 = x^2 + y^2$.

Lời giải
  • $(xy-6)^2-(x+y)^2==-13$
  • $(xy-x-y-6)(xy+x+y-6) = -13$.
  • TH1:$xy – x-y-6 = -13, xy+x+y-6 = 1$.
  • TH2:$xy-x-y-6 = -1, xy+x+y-6 = 13$.
  • Giải ra nghiệm $(x;y)$ là $(3;4), (4;3), (7;0), (0;7)$.

Ví dụ 3. Giải nghiệm nguyên dương của phương trình $$x(y^2-p) + y(x^2-p) = 5p$$ trong đó $p$ là số nguyên tố.

Lời giải
  •  Biến đổi pt thành $(x+y)(xy-p) = 5p$.
  • TH1: $x+y = 5, xy – p = p$, giải ra được $(x;y,p)$ là $(1;4;2),(4;1;2), (2;3;3), (3;2;3)$.
  • TH2: $x+y = p, xy-p=5$, ta có $xy – x-y = 5 \Leftrightarrow (x-1)(y-1) = 6$.
    $(x;y;p)$ là $(3;4;7), (4;3;7)$.
  • H3: $x+y=5p, xy-p = 1$, ta có $5xy -x-y = 5 \Leftrightarrow (5x-1)(5y-1) = 26$. (Vô nghiệm).

Ví dụ 4. Giải phương trình trong tập các số nguyên dương $$x + x^2 + x^3 = y+y^2$$.

Lời giải
  • $x^3 = (y-x)(y+x+1)$.
  • Khi đó nếu $p$ là ước nguyên tổ của $y-x, y+x+1$ thì $p = 1$(vô lí). Do đó $(y-x, y+x+1) = 1$.
  • $y-x = a^3, y+x+1 = b^3$ và $ab=x$.
  • $b^3-a^3 = 2ab+1$, vì $b \geq a+1$, suy ra $b^3-a^3 = (b-a)(a^2+b^2+1) > 2ab+1$ phương trình vô nghiệm.

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

Bài 1. Giải các phương trình sau trong tập nguyên dương:
a) $ 2x^2+3xy-2y^2=7 $.
b) $ x^3-xy=6x-5y-8 $
c) $ x^3-y^3=91 $.
Bài 2. Giải phương trình nghiệm nguyên $$\dfrac{1}{x}+\dfrac{1}{y} = \dfrac{1}{2020}$$
Bài 3. Tìm các số nguyên $x$, $y$ sao cho:
a) $3^x-y^3=1$;
b) $1+x+x^2+x^3=2^y$;
c) $1+x+x^2+x^3=2003^y$.
Bài 4. Tìm các số nguyên tố $x$, $y$, $z$ thỏa mãn: $x^y+1=z$
Bài 5. Tìm các số nguyên dương $x, y,z$ thỏa $y$ nguyên tố và $y, 3$ không là ước của $z$ thỏa $x^3-y^3=z^2$.

Phương trình nghiệm nguyên – P1

Leave a reply

Tiếp theo chuyên mục số học dành cho các em lớp 8, 9 thi học sinh giỏi và thi vào 10, hôm nay là bài giảng về phương trình nghiệm nguyên.

Phương trình nghiệm nguyên là một trong những phần hay và khó nhất của số học, nhiều phương trình có vẻ rất đơn giản nhưng lại rất khó để giải, đó là một trong những điều thú vị cuốn hút nhiều học sinh đam mê toán học. Trong bài này chúng tôi xin nêu ra một vài phương pháp giúp các em bước đầu tiếp cận với việc giải phương trình nghiệm nguyên.

Phương pháp biến đổi thành tổng. Phương pháp này dựa trên tính chất: Mỗi số nguyên dương đều được biểu diễn thành tổng của hai hay nhiều số nguyên dương khác trong hữu hạn các trường hợp. Vì thế ta có thể xét những trường hợp này để cho ra cách giải, ngoài ra ta có thể đánh giá để đưa về ít trường hợp để xét hơn, giúp lời giải ngắn gọn hơn.

Ví dụ 1. Giải các phương trình sau trong tập số nguyên

a) $x^2 + 3y^2 = 13$.

b) $2^x + y^4 = 85$.

c) $x^2 + y^2 + x + y – xy = 0$.

Lời giải

a) Ta biểu diễn 13 thành tổng của một số chính phương và một số khác:

$13 = 0^2 +13 = 1^2 + 12= 2^2 + 9 = 3^2 + 4$.

Trong các cách biểu diễn trên thì chỉ có $1^2 +12 = 1^2 + 3\cdot 2^2$ thỏa đề bài. Khi đó $x = \mp 1, y = \mp 2$.

Phương trình có 4 nghiệm $(-1;-2), (-1,2), (1,-2), (1,2)$.

b) Cũng có thể giải như trên, nhưng ta thêm một chút đánh giá cho lời giải gọn hơn, có thể đánh giá theo $x, y$.

Ta có $y^4 =85 – 2^x < 84 \Rightarrow |y| \leq 3$.

  • Nếu $|y| = 0, 2^x = 85$ (loại).
  • Nếu $|y|=1, 2^x = 84$ (loại).
  • Nếu $|y| = 2, 2^x = 69$ (loại).
  • Nếu $|y| = 3, 2^x = 4, x = 2$.

Từ đó phương trình có nghiệm là $(2,-3), (2,3)$.

Ví dụ 2. Giải phương trình nghiệm nguyên $x^2 – 6xy + 14y^2-10y – 16 = 0$

Lời giải

Phương trình tương đương với $$(x-3y)^2 + 5(y-1)^2=21$$
Khi đó $5(y-1)^2 \leq 21 \Rightarrow (y-1)^2 <5$.

  • Nếu $(y-1)^2 = 0 \Rightarrow y = 1, (x-3)^2 = 21$(vô lý)
  • Nếu $(y-1)^2 = 1 \Rightarrow (x-3y)^2 = 16$ giải ra được $(x;y)$ là $(4;0), (-4;0), (12;2), (2;2)$.
  • Nếu $(y-1)^2 = 4 \Rightarrow (x-3y)^2 = 1$, giải ra được $(x;y)$ là $(10;3), (8;3), (-2;-1), (-4;-1)$.
    Vậy phương trình có 8 nghiệm.

Ví dụ 3. Giải phương trình nghiệm nguyên $2x^2- 2xy + 5y^2 = 41$.

Lời giải
  •  $(x-y)^2 + x^2 + 4y^2 = 41$.
  • $4y^2 < 41$ do đó $y \in \{0, 1, 2, 3, -1, -2, -3\}$
  • $(-1;-3), (-2;-3), (1;3)$ và $(2;3)$.

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

Bài 1. Giải các phương trình sau trong tập số nguyên:
a)  $19x^2+28y^2=2001$.
b) $3x^2 + y^2 – 4y = 24$.
c) $2^x + 5y^2 = 38$.
d) $x^2 – 6xy+13y^2 = 100$.
Bài 2. Giải các phương trình trong tập số nguyên:
a) $2x^2 + 6y^2 + 7xy – x- y = 25$.
b) $x^2 -xy+y^2 = x+y$

(còn nữa)

Bài tập chứng minh chia hết – Ôn thi vào lớp 10

Leave a reply

Các bài toán chứng minh chia hết trong chương trình ôn thi vào lớp 10, dành cho các em rèn luyện.

Bài 1. (Lâm Đồng 2018 – 2019)

Với $ n $ là số tự nhiên chẵn, chứng minh rằng: $$ (20^n+16^n-3^n-1)\ \vdots \ 323. $$
Bài 2. Chứng minh rằng với mọi số tự nhiên $n$ thì $5^{2n}+7$ chia hết cho 8.
Bài 3. (Bến Tre 2018 – 2019)
Cho $ p $ là số nguyên tố lớn hơn 3. Chứng minh rằng $ p^2-1 $ chia hết cho 24.
Bài 4.  Chứng minh rằng với mọi số tự nhiên $n$ thì $3^{3n+1} + 2^{n+2}$ chia hết cho 7.
Bài 5. Chứng minh rằng nếu $\overline{abc}$ chia hết cho 37 thì $\overline{bca}$ cũng chia hết cho 37.
Bài 6. Chứng minh rằng với mọi số tự nhiên $n$ thì $(22n+7,33n+10)=1$
Bài 7. Chứng minh rằng nếu $a, b$ là các số nguyên thỏa $a^2 + b^2$ chia hết cho 3 thì cả hai số $a, b$ đều chia hết cho 3.

Bài 8. Tìm tất cả các số tự nhiên $n$ để $3^n + 5^n$ chia hết cho $3^{n-1} + 5^{n-1}$.
Bài 9. Cho $n$ là số tự nhiên không chia hết cho 2 và 3. Chứng minh rằng với mọi số tự nhiên $k$ thì ${\left( {k + 1} \right)^n} – {k^n} – 1$ chia hết cho ${k^2} + k + 1$
Bài 10. Tìm tất cả các số nguyên dương $n$ sao cho $(n-1)!$ không chia hết cho $n$.
Bài 11. Chứng minh rằng nếu $n$ không chia hết cho 7 thì $n^3-1$ hoặc $n^3+1$ chia hết cho 7.

Bài 12. (Tuyên Quang 2018 – 2019) Cho $a$, $b$, $c$ là các số nguyên. Chứng minh rằng: nếu $ a^{2016}+b^{2017}+c^{2018} $ chia hết cho 6 thì $ a^{2018}+b^{2019}+c^{2020} $ cũng chia hết cho 6.

Bài 13. Cho các số nguyên $x, y, z$ thỏa $(x-y)(y-z)(z-x) = x+ y + z$. Chứng minh rằng $x + y + z$ chia hết cho 27.
Bài 14. Chứng minh rằng với mọi số nguyên $a, b, c$ thì $abc(a^3-b^3)(b^3-c^3)(c^3-a^3)$ chia hết cho 7.
Bài 15. Cho tập $A= {1,2,3,4,5,6,7}$. Gọi S là tập tất cả các số tự nhiên có 7 chữ số khác nhau lấy từ A. Chứng minh rằng không tồn tại hai số $b, c$ thuộc S sao cho $b$ chia hết cho $c$.
Bài 16.  Cho các số nguyên $x, y, z$ khác 0.\ Đặt $x^2 – yz = a, y^2- xz = b, z^2 – xy = c$. \Chứng minh rằng $ax+by + cz $ chia hết cho $a+b+c$.
Bài 17.  Chứng minh rằng trong một 100 số tự nhiên thì có một số hoặc một vài số có tổng chia hết cho 100.
Bài 18.  Chứng minh rằng trong tập mọi tập con có $n+1$ phần tử của tập ${1, 2, \cdots, 2n}$ thì luôn có hai số $a, b$ sao cho $a$ chia hết cho $b$.
Bài 19.  (PTNK 2019)
a) Tìm tất cả những số tự nhiên $n$ sao cho $2^n+1$ chia hết cho 9.
b) Cho $n$ là số tự nhiên $n>3$. Chứng minh rằng $2^n+1$ không chia hết cho $2^m-1$ với mọi số tự nhiên $m$ sao cho $2 < m \leq n$.
Bài 20. Cho hai số nguyên dương $m$, $n$ thỏa mãn $m+n+1$ là một ước nguyên tố của $2\left( m^2+n^2-1\right) $.
Chứng minh rằng $ m\cdot n $ là số chính phương.
Bài 21. Có bao nhiêu số tự nhiên $n$ không vượt quá $2019$ thỏa mãn $n^3+2019$ chia hết cho $6$.
Bài 22. (Đại học KHTN Hà Nội 2018 – 2019) Cho $x$, $y$ là các số nguyên sao cho $ x^2-2xy-y^2$; $xy-2y^{2}-x$ đều chia hết cho 5. Chứng minh $ 2x^2+y^2+2x+y$ cũng chia hết cho 5.
Bài 23. Cho $n$ số nguyên dương tùy ý, với mỗi số nguyên $k$ ta đặt $S_k=1^k+2^k+….+n^k $. Chứng minh rằng: $S_{2019}\ \vdots \ S_1 $.
Bài 24.  (Vinh 2018 – 2019) Cho số tự nhiên $ n\geq2 $ và số nguyên tố $p$ thỏa mãn $ p-1 $ chia hết cho $n$ đồng thời $ n^3-1 $ chia hết cho $p$. Chứng minh rằng $ n+p $ là một số chính phương.
Bài 25. Cho hai số $m,n$ nguyên dương lẻ nguyên tố cùng nhau và $m^2 + 2 \, \vdots \, n$ và $n^2 + 2 \, \vdots \, m$.  Chứng minh rằng $m^2 + n^2 + 2$ chia hết cho $4mn$.
Bài 26. Cho các số $m,n$ nguyên dương thỏa $5m + n$ chia hết cho $5n+m$. Chứng minh $m$ chia hết cho $n$.
Bài 27. Cho các số $x,y$ nguyên dương thỏa $x^2 + y^2 + 10$ chia hết cho $xy$.
a)  Chứng minh rằng $x,y$ là hai số lẻ và nguyên tố cùng nhau.
b) Chứng minh rằng $k = \dfrac{x^2+y^2+10}{xy}$ chia hết cho 4 và $k \geq 12$.

Hết

 

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.