BITEXEDU Chuyên trang chia sẻ tài liệu, kinh nghiệm ứng dụng giải toán trên máy tính cầm tay
Định lý phần dư Trung hoa
- 09/08/2024
- 643 lượt xem
| Dạng 1. Hệ hai phương trình đồng dư. |
| Tìm 3 chữ số cuối cùng của số $x=1.3.5.7\dots 2021.2023$ |
Có $1012$ số lẻ từ $1$ đến $2023$.
| $1\equiv 1\ \text{(mod 8)} $
$3\equiv 3\ \text{(mod 8)} $ $5\equiv 5\ \text{(mod 8)} $ $7\equiv 7\ \text{(mod 8)} $ |
 |
…………………………
$9\equiv 1\ \text{(mod 8)} $
$11\equiv 3\ \text{(mod 8)} $
$13\equiv 5\ \text{(mod 8)} $
$15\equiv 7\ \text{(mod 8)} $
……………………….
| $2017\equiv 1\ \text{(mod 8)} $
$2019\equiv 3\ \text{(mod 8)} $ $2021\equiv 5\ \text{(mod 8)} $ $2023\equiv 7\ \text{(mod 8)} $ |
 |
Vậy $1012$ số lẻ từ $1$ đến $2023$ chia thành $\dfrac{1012}{4}=253$ “bộ tứ”, mỗi bộ tứ có tích đồng dư với $1$ (mod 8). Vậy $x \equiv 1\ \text{(mod 8)} $. Ngoài ra $x$ chia hết cho $125$ (vì chứa thừa số $125$), nên $x \equiv 0\ \text{(mod 125)} $.
Tóm lại ta có hệ phương trình đồng dư: $$\left\lbrace\begin{array}{l}x \equiv 1\ \text{(mod 8)}\\
x \equiv 0\ \text{(mod 125)} \end{array} \right. $$
Vì $8$ và $125$ nguyên tố cùng nhau nên theo định lý phần dư Trung Hoa, hệ phương trình có nghiệm duy nhất $$x=1.125.z_1+0.8.z_2+k.8.125$$
trong đó $z_1$ là nghịch đảo của $125$ theo mô-đu-lô $8$ và $z_2$ là nghịch đảo của $8$ theo mô-đu-lô $125$.
Sử dụng bảng tính ta có $z_1=5$ (kiểm tra 
).
Vậy $x=625+1000k$, nghĩa là 3 chữ số cuối cùng của $x$ là $625$.
| Dạng 2. Hệ ba phương trình đồng dư. |
| Tìm số tự nhiên $x$ nhỏ nhất có $10$ chữ số, biết $x$ chia cho $17$ dư $11$, chia cho $19$ dư $15$ và chia cho $23$ dư $19$. |
Xét hệ phương trình đồng dư: $$\left\lbrace\begin{array}{ll}
x \equiv 11 & \text{mod}\ 17\\
x \equiv 15 & \text{mod}\ 19\\
x \equiv 19 & \text{mod}\ 23
\end{array} \right. $$
Vì $17, 19, 23$ nguyên tố cùng nhau nên hệ phương trình có nghiệm duy nhất
trong đó $ z_1, z_2, z_3$ lần lượt là nghịch đảo mô-đu-lô của $ 19.23, 17.23, 19.17$ theo mô-đu-lô $ 17, 19, 23$ tương ứng.
Thực hiện thuật toán nghịch đảo mô-đu-lô trên bảng tính của máy tính Casio fx-880BTG ta có: $ z_1=10, z_2=7, z_3=1$. (xem bài đọc thêm 1. ở dưới)
Vậy
Vì $ x \geqslant 10^9 \Leftrightarrow k \geqslant \dfrac{10^9-95262}{7429} \approx 134594,7958$. Vì $ k \in \mathbb{Z}$ nên $ k$ nguyên nhỏ nhất thoả yêu cầu bài toán là $ k=134595$.
Do đó Số cần tìm $ x=95262+7429\times 134595=1000001517$.
| Đọc thêm. 1. Giải hệ phương trình đồng dư. 2. Giải hệ phương trình đồng dư (tiếp theo) |
 |
About TS. Nguyễn Thái Sơn
