Chào các em học sinh yêu quý của thầy!

Hôm nay, chúng ta sẽ cùng nhau giải một bài toán rất thú vị về phép chia có dư. Bài toán yêu cầu chúng ta tìm số dư của phép chia \(19^{24} – 15^{12}\) cho \(2004\).

Nghe có vẻ “khủng khiếp” với các số mũ lớn phải không? Nhưng đừng lo, chúng ta sẽ dùng kiến thức về số học đồng dư (modular arithmetic) mà chúng ta đã học để giải quyết bài toán này một cách khéo léo nhé!

Chiến lược giải quyết:

1. Phân tích số chia \(2004\) thành các thừa số nguyên tố.
2. Tìm số dư của biểu thức \(19^{24} – 15^{12}\) khi chia cho từng thừa số nguyên tố (hoặc lũy thừa của chúng).
3. Kết hợp các kết quả đó lại để tìm số dư cuối cùng khi chia cho \(2004\).

Bắt đầu nào!

Bước 1: Phân tích số chia \(2004\)

Chúng ta có:
\(2004 = 2 \times 1002 = 2 \times 2 \times 501 = 2^2 \times 3 \times 167\)

Vậy, chúng ta sẽ cần tìm số dư của biểu thức khi chia cho \(4\), cho \(3\) và cho \(167\).

Bước 2: Tìm số dư của \(19^{24} – 15^{12}\) khi chia cho \(3\), \(4\) và \(167\)

A. Tìm số dư khi chia cho \(3\):

Ta có:

• \(19 \equiv 1 \pmod{3}\)
• \(15 \equiv 0 \pmod{3}\)

Do đó:

\(19^{24} – 15^{12} \equiv 1^{24} – 0^{12} \pmod{3}\)
\( \equiv 1 – 0 \pmod{3}\)
\( \equiv 1 \pmod{3}\)

Vậy, số dư khi chia cho \(3\) là \(1\).

B. Tìm số dư khi chia cho \(4\):

Ta có:

• \(19 \equiv 3 \equiv -1 \pmod{4}\)
• \(15 \equiv 3 \equiv -1 \pmod{4}\)

Do đó:

\(19^{24} – 15^{12} \equiv (-1)^{24} – (-1)^{12} \pmod{4}\)
\( \equiv 1 – 1 \pmod{4}\)
\( \equiv 0 \pmod{4}\)

Vậy, số dư khi chia cho \(4\) là \(0\). Điều này có nghĩa là biểu thức chia hết cho \(4\).

C. Tìm số dư khi chia cho \(167\):

Số \(167\) là một số nguyên tố. Chúng ta sẽ tính từng phần một:

1. Tính \(19^{24} \pmod{167}\):

Ta sẽ dùng phương pháp lũy thừa nhanh (bình phương liên tiếp):

• \(19^1 \equiv 19 \pmod{167}\)
• \(19^2 = 361\)
  \(361 = 2 \times 167 + 27 \implies 19^2 \equiv 27 \pmod{167}\)
• \(19^4 \equiv 27^2 = 729\)
  \(729 = 4 \times 167 + 61 \implies 19^4 \equiv 61 \pmod{167}\)
• \(19^8 \equiv 61^2 = 3721\)
  \(3721 = 22 \times 167 + 47 \implies 19^8 \equiv 47 \pmod{167}\)
• \(19^{16} \equiv 47^2 = 2209\)
  \(2209 = 13 \times 167 + 38 \implies 19^{16} \equiv 38 \pmod{167}\)

Bây giờ, để tính \(19^{24}\), ta phân tích \(24 = 16 + 8\):

\(19^{24} = 19^{16} \times 19^8 \pmod{167}\)
\( \equiv 38 \times 47 \pmod{167}\)
\( \equiv 1786 \pmod{167}\)

Ta có: \(1786 = 10 \times 167 + 116\)

Vậy, \(19^{24} \equiv 116 \pmod{167}\).

2. Tính \(15^{12} \pmod{167}\):

Tương tự, dùng phương pháp lũy thừa nhanh:

• \(15^1 \equiv 15 \pmod{167}\)
• \(15^2 = 225\)
  \(225 = 1 \times 167 + 58 \implies 15^2 \equiv 58 \pmod{167}\)
• \(15^4 \equiv 58^2 = 3364\)
  \(3364 = 20 \times 167 + 24 \implies 15^4 \equiv 24 \pmod{167}\)
• \(15^8 \equiv 24^2 = 576\)
  \(576 = 3 \times 167 + 75 \implies 15^8 \equiv 75 \pmod{167}\)

Bây giờ, để tính \(15^{12}\), ta phân tích \(12 = 8 + 4\):

\(15^{12} = 15^8 \times 15^4 \pmod{167}\)
\( \equiv 75 \times 24 \pmod{167}\)
\( \equiv 1800 \pmod{167}\)

Ta có: \(1800 = 10 \times 167 + 130\)

Vậy, \(15^{12} \equiv 130 \pmod{167}\).

3. Tính \(19^{24} – 15^{12} \pmod{167}\):

\(19^{24} – 15^{12} \equiv 116 – 130 \pmod{167}\)
\( \equiv -14 \pmod{167}\)

Vì số dư phải là một số không âm, ta cộng thêm \(167\):

\( \equiv -14 + 167 \pmod{167}\)
\( \equiv 153 \pmod{167}\)

Vậy, số dư khi chia cho \(167\) là \(153\).

Bước 3: Kết hợp các kết quả

Chúng ta có hệ đồng dư sau:

1. \(x \equiv 1 \pmod{3}\)
2. \(x \equiv 0 \pmod{4}\)
3. \(x \equiv 153 \pmod{167}\)

Từ (2), ta biết \(x\) là một bội số của \(4\). Từ (1), ta biết \(x\) chia \(3\) dư \(1\).
Các bội của \(4\) là \(4, 8, 12, 16, \dots\)
Kiểm tra số dư khi chia cho \(3\):
\(4 \equiv 1 \pmod{3}\)
Vậy, \(x \equiv 4 \pmod{3 \times 4}\), tức là \(x \equiv 4 \pmod{12}\).

Bây giờ chúng ta cần giải hệ:

• \(x \equiv 4 \pmod{12}\)
• \(x \equiv 153 \pmod{167}\)

Từ \(x \equiv 4 \pmod{12}\), ta có thể viết \(x = 12k + 4\) cho một số nguyên \(k\).

Thay vào phương trình thứ hai:

\(12k + 4 \equiv 153 \pmod{167}\)
\(12k \equiv 153 – 4 \pmod{167}\)
\(12k \equiv 149 \pmod{167}\)

Để tìm \(k\), chúng ta cần tìm nghịch đảo của \(12\) theo modulo \(167\). Chúng ta có thể dùng thuật toán Euclid mở rộng:

\(167 = 13 \times 12 + 11 \Rightarrow 11 = 167 – 13 \times 12\)
\(12 = 1 \times 11 + 1 \Rightarrow 1 = 12 – 1 \times 11\)

Thay \(11\) vào biểu thức của \(1\):

\(1 = 12 – 1 \times (167 – 13 \times 12)\)
\(1 = 12 – 167 + 13 \times 12\)
\(1 = 14 \times 12 – 1 \times 167\)

Từ đây, ta thấy \(14 \times 12 \equiv 1 \pmod{167}\). Vậy, nghịch đảo của \(12\) modulo \(167\) là \(14\).

Nhân cả hai vế của \(12k \equiv 149 \pmod{167}\) với \(14\):

\(14 \times 12k \equiv 14 \times 149 \pmod{167}\)
\(1k \equiv 2086 \pmod{167}\)

Để tìm số dư của \(2086\) khi chia cho \(167\):

\(2086 = 12 \times 167 + 82\)

Vậy, \(k \equiv 82 \pmod{167}\).

Điều này có nghĩa là \(k = 167m + 82\) cho một số nguyên \(m\).

Thay \(k\) trở lại vào biểu thức của \(x\):

\(x = 12k + 4\)
\(x = 12(167m + 82) + 4\)
\(x = 12 \times 167m + 12 \times 82 + 4\)
\(x = 2004m + 984 + 4\)
\(x = 2004m + 988\)

Vậy, \(x \equiv 988 \pmod{2004}\).

Kiểm tra lại:

• \(988 \pmod 3\): \(9+8+8=25\). \(25 \div 3\) dư \(1\). (Đúng!)
• \(988 \pmod 4\): \(88\) chia hết cho \(4\). (Đúng!)
• \(988 \pmod{167}\): \(988 = 5 \times 167 + 153\). (Đúng!)

Kết luận:

Số dư của phép chia \(19^{24} – 15^{12}\) cho \(2004\) là \(988\).

Thầy hy vọng qua bài giải chi tiết này, các em đã hiểu rõ hơn về cách áp dụng kiến thức đồng dư để giải các bài toán “khó nhằn” với các con số lớn. Hãy luôn tự tin và kiên trì khi giải toán nhé!