Đồng dư thức Archives

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^{2 n} + 12 \cdot 6^{n}$ chia hết cho 19.
b) $5^{2 n + 1} + 2^{n + 4} + 2^{n + 1}$ chia hết cho 23.

Lời giải

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

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

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

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

Khi đó $5^{2 n + 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^{2 n + 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^{2 n} + 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^{4 k + r} \equiv 2^{r} (\mod 5)$ .

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

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

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

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

Đặt $n = 6 k + r (0 \leq r \leq 5)$ . Khi đó $2^{n} + 1 \equiv 2^{6 k + 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 = 6 k + 3$ với $k$ là số tự nhiên.

Ví dụ 3. Cho $a_{n} = 2^{2 n + 1} + 2^{n + 1} + 1$ và $b_{n} = 2^{2 n + 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_{n} b_{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^{4 n + 2} + 1 \equiv 0 (\mod 5)$ .
$a_{n} + b_{n} = 2^{2 n + 2} + 2 \equiv 4 (- 1)^{n} + 2 (\mod 5) \equiv 1, - 2 (\mod 5)$ .

Do đó $a_{n} b_{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 (mod 3) \Rightarrow 2018^{n} \equiv 1964^{n} (mod 3) .$
$2032 \equiv 1984 (mod 3) \Rightarrow 2032^{n} \equiv 1984^{n} (mod 3)$ .
$\Rightarrow A_{n} ⋮ 3.$
Ta lại có $2018 \equiv 1984 (mod 17) \Rightarrow 2018^{n} \equiv 1984^{n} (mod 17)$ .
$2032 \equiv 1964 (mod 17) \Rightarrow 2032^{n} \equiv 1964^{n} (mod 17)$ .
$\Rightarrow A_{n} ⋮ 17.$
Do $(3; 17) = 1$ nên $A_{n} ⋮ 51 \forall n$
b) $A_{n} = 2018^{n} + 2032^{n} - 1964^{n} - 1984^{n} .$

Ta xét các trường hợp của $n$ để $A_{n} ⋮ 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$ (mod 5) $(loại)$ .
Nếu $n = 4 k \Rightarrow A_{n} \equiv 2 \cdot 2^{4 k} - 2 \equiv 2 - 2 \equiv 0$ (mod 5) (nhận)
Nếu $n = 4 k + 2 \Rightarrow A_{n} \equiv 2 \cdot 2^{4 k + 2} - 2 \equiv 8 - 2 \equiv 6$ (mod 5) (loại).
Vậy $A_{n} ⋮ 5 \Leftrightarrow n ⋮ 4.$
Ta xét các trường hợp của $n$ để $A_{n} ⋮ 9.$
Ta có
$A_{n} \equiv 2^{n} + (- 2)^{n} - 2^{n} - 4^{n} (\mod 9)$
$\equiv 2^{n} - 4^{n} (mod 9) \quad (Do n chẵn).$
$\equiv 2^{n} (1 - 2^{n}) \mod 9) V ì$ (2;9 ) = 1 \Rightarrow 2^n – 1 \vdots \ 9 $. X é t$ n= 3k $v ớ i$ k \in \mathbb{N} $. T a c ó$ A_n \equiv 2^{3k} – 1 \equiv (-1)^k – 1 \quad (\mod 9) \Rightarrow k$ chẵn.
- Xét $n = 3 k + 1$ với $k \in N$ . Ta có $A_{n} \equiv 2^{3 k + 1} - 1 \equiv 2 \cdot (- 1)^{k} - 1 (mod 9) \quad (loại) .$
- Xét $n = 3 k + 2$ với $k \in N$ . Ta có $A_{n} \equiv 2^{3 k + 2} - 1 \equiv 4 \cdot (- 1)^{k} - 1 (mod 9) \quad (loại) .$
Vậy $A_{n} ⋮ 45 \Leftrightarrow n ⋮ 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^{2 n + 1} + 2^{n + 4} + 2^{n + 1}$ chia hết cho $23$ ;
b) $11^{n + 2} + 12^{2 n + 1}$ chia hết cho $133$ ;
c) $5^{n + 2} + {26.5}^{n} + 8^{2 n + 1}$ chia hết cho $59$ ;
d) $5^{2 n + 1} {.2}^{n + 2} + 3^{n + 2} {.2}^{2 n + 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^{3 n + 4} + 3^{2 n + 1}$ chia hết cho 19
b) $n {.2}^{n} + 1$ chia hết cho 3
c) $2^{2} n + 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^{2 n}} + 10$ chia hết cho $13$ ;
b) $3^{2^{4 n + 1}} + 2^{3^{4 n + 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$ .

Đị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 (m o d n)$ (đọc là $a$ đồng dư $b$ theo modul $n$ ).

Nhận xét. $a \equiv b (m o d n) \Leftrightarrow (a - b) ⋮ n$

Ví dụ 1. $28 \equiv 3 (m o d 5)$

Đị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 (m o d n), b \equiv c (m o d n)$ thì $a \equiv c (m o d n)$
2) Nếu $a \equiv b (m o d n)$ thì $a \pm c \equiv b \pm c (m o d n)$ với mọi số nguyên c.
3) Nếu $a \equiv b (m o d n), c \equiv d (m o d n)$ thì $a + c \equiv b + d (m o d n)$
4) Nếu $a \equiv b (m o d n)$ thì $c . a \equiv c . b (m o d n)$ với mọi số nguyên c.
5) $a \equiv b (m o d n)$ thì $a^{k} \equiv b^{k} (m o d n)$ với mọi số nguyên dương k. Đặc biệt nếu $a \equiv 1 (m o d n)$ thì $a^{k} \equiv 1 (m o d n)$

Chứng minh

1) Ta có

a - c = a - b + b - c

, mà

a \equiv b (m o d n), b \equiv c (m o d n)

nên

a - b ⋮ n, b - c ⋮ n

, do đó

a - c ⋮ n

hay

a \equiv c (m o d n)

.
2)

a - b = (a \pm c) - (b \pm c)

, do đó

a \equiv b (m o d n) \Leftrightarrow a \pm c \equiv b \pm c (m o d n)

a + c - (b + d) = (a - b) + (c - d) ⋮ n

, suy ra

a + c \equiv b + d (m o d n)

4) Do

a \equiv b (m o d n)

nên

a - b ⋮ n \Rightarrow c a - c b ⋮ n

với mọi số nguyên c. Do đó

c a \equiv c b (m o d n)

.
5) Ta có

(a^{k} - b^{k}) ⋮ (a - b)

với mọi số tự nhiên k. Do đó nếu

a \equiv b (m o d n)

thì

a^{k} \equiv b^{k} (m o d n)

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

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

Đị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 (m o d m_{1}), a \equiv b (m o d m_{2})$ và $(m_{1}, m_{2}) = 1$ thì $a \equiv b (m o d 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^{2 n + 1}$ chia hết cho 13.

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

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

Bài 5. Tìm số nguyên dương nhỏ nhất m biết $m \equiv 2 (m o d 6), m \equiv 2 (m o d 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 (m o d 3)$ , chứng minh $a \equiv 0 (m o d 3), b \equiv 0 (m o d 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} (m o d m)$ với i = 1, 2, …,n thì

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

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

Trong đó $\sum_{i = 1}^{n} x_{i} = x_{1} + x_{2} + \dots + x_{n}, \prod_{i = 1}^{n} x_{i} = x_{1}, x_{2} \dots x_{n}$ .

Toán Việt

Chia sẻ và học hỏi

Category Archives: Đồng dư thức

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

Đồng dư