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$.
2. Ta sử dụng định lý Fermat hoặc định lý Euler để tính số dư của lũy thừa lớn modulo một số.
3. Tính $\gcd(2004,1975)$ để kiểm tra tính nguyên tố tương đối:
$$\gcd(2004,1975) = 1$$
Do đó, ta có thể áp dụng định lý Euler.
4. Tính $\varphi(1975)$, trong đó $1975 = 25 \times 79$.
- $\varphi(25) = 25 \times (1 - \frac{1}{5}) = 20$
- $\varphi(79) = 79 - 1 = 78$ (vì 79 là số nguyên tố)
Vậy:
$$\varphi(1975) = \varphi(25) \times \varphi(79) = 20 \times 78 = 1560$$
5. Theo định lý Euler:
$$2004^{1560} \equiv 1 \pmod{1975}$$
6. Ta cần tính $2004^{376} \pmod{1975}$.
7. Rút gọn cơ số modulo 1975:
$$2004 \equiv 2004 - 1975 = 29 \pmod{1975}$$
Vậy:
$$2004^{376} \equiv 29^{376} \pmod{1975}$$
8. Ta tính $29^{376} \pmod{1975}$ bằng phương pháp lặp bình phương và nhân (modular exponentiation).
9. Kết quả tính được:
$$29^{376} \equiv 676 \pmod{1975}$$
10. Vậy số dư của $2004^{376}$ khi chia cho $1975$ là $676$.