Question: tìm số dư của $2004^{376}$ chia cho $1975$
1. Bài toán yêu cầu tìm số dư của $2004^{376}$ khi chia cho $1975$. Đây là bài toán về tính toán số dư của lũy thừa lớn modulo một số.
2. Công thức sử dụng: Để tính $a^b \bmod m$, ta có thể sử dụng định lý Fermat hoặc thuật toán lũy thừa nhanh (modular exponentiation).
3. Bước đầu tiên, ta rút gọn cơ số $2004$ modulo $1975$:
$$2004 \equiv 2004 - 1975 = 29 \pmod{1975}$$
4. Vậy bài toán trở thành tính $29^{376} \bmod 1975$.
5. Ta sẽ sử dụng thuật toán lũy thừa nhanh để tính $29^{376} \bmod 1975$:
- Viết $376$ dưới dạng nhị phân: $376 = 256 + 64 + 32 + 16 + 8$.
- Tính lần lượt các lũy thừa:
- $29^1 \equiv 29 \pmod{1975}$
- $29^2 \equiv 29^2 = 841 \pmod{1975}$
- $29^4 \equiv 841^2 \bmod 1975$
- Tiếp tục nhân và lấy modulo cho đến $29^{376}$.
6. Do tính toán thủ công rất phức tạp, ta có thể sử dụng máy tính hoặc phần mềm để tính chính xác số dư.
7. Kết quả cuối cùng là số dư của $29^{376}$ khi chia cho $1975$.
Tóm lại, số dư của $2004^{376}$ chia cho $1975$ bằng số dư của $29^{376}$ chia cho $1975$.
(Do giới hạn về tính toán thủ công, bạn nên sử dụng công cụ tính toán để có kết quả chính xác.)