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
Hệ phương trình đồng dư
- 30/08/2025
- 551 lượt xem
| Đặt vấn đề. Bài thi HSG MTCT THCS những năm 2010 luôn có bài toán về hệ phương trình đồng dư. Học sinh sẽ chuyển thành hệ phương trình thông thường và giải được bài toán. Sau đó bài thi này ở cấp Quận/huyện được nâng lên phức tạp hơn. Để giải được bài toán đó, nhiều GV phụ trách đội tuyển đã dùng Định lý phần dư Trung Hoa (CRT), trong đó có nội dung kiến thức mới là tìm nghịch đảo mô-đu-lô của một số $a$ mod $m$, là một nội dung cơ bản của Tin học.
Cách đây 4 năm khi Máy tính Casio fx-880BTG ra đời, Thầy Sơn đã giới thiệu thuật toán tìm nghịch đảo mô-đu-lô trên bảng tính. Hôm nay chúng ta sẽ giải lại bài toán cấp Thành phố (nghịch đảo của $a$ không quá $40$ và sử dụng định nghĩa để tìm nghịch đảo mô-đu-lô). Bài viết sau sẽ nói về Thuật Toán và giải bài thi cấp Quận/Huyện (cũ) dùng CRT. |
 |
Xét hệ phương trình $$\left\lbrace\begin{array}{l}
x \equiv 3 \quad (\text{mod}\ 17 )\\
x \equiv 1 \quad (\text{mod}\ 23 )\\
x \equiv 4 \quad (\text{mod}\ 29 )\end{array} \right. $$
Vì $17, 23, 29$ nguyên tố cùng nhau từng đôi một nên theo Định lý Phần dư Trung Hoa (CRT), hệ phương trình có nghiệm duy nhất: $$x = \underbrace{3\times 23\times 29z_1+1\times 17\times 29z_2+4\times 23\times 17z_3}_{B} +\underbrace{17\times 23\times 29}_{A}k, k \in \mathbb{Z}$$
trong đó $z_1, z_2, z_3$ lần lượt là nghịch đảo của $23\times 29, 17\times 29, 23\times 17$ tương ứng với mô-đu-lô $17, 23, 29$.
| 1. | Nếu ta đặt $A=17\times 23 \times 29$ thì $23\times 29=\dfrac{A}{17}, 17\times 29=\dfrac{A}{23}, 23\times 17 =\dfrac{A}{29}$. |
| 2. | Lưu $17\times 23 \times 29$ vào A:  |
| 3. | Mở bảng tính, điền công thức để đánh số từ 1 đến 44 vào $A_2$ đến $A_{45}$, nhập 17 (mod) vào $B_1$ (lưu ý $B_1$ là |
một địa chỉ cố dịnh trong bảng tính)  . |
| 4. | Để tìm nghịch đảo của $17\times 23$ ta thực hiện phép tính $\dfrac{\dfrac{A}{17}x-1}{17}$ nếu kết quả là số nguyên thì $x$ tương ứng là |
nghịch đảo của $17\times 23$ theo mô-đu-lô 17:  . vậy $z_1=13$. |
| 5. | Trong bảng tính ta thay $B_1$ bằng $23$ kết quả $z_2=7 $ và thay $B_1$ bằng $29$ kết quả $z_3=27$. |
Vì $x$ có ít nhất 11 chữ số nên $x\geqslant 10^{10} ⇒ k \geqslant 1+ \text{Int} \dfrac{10^{10}-B}{A} $. Nhắc lại $17\times 23\times 29$ lưu vào A, $3\times 23\times 29z_1+1\times 17\times 29z_2+4\times 23\times 17z_3$ lưu vào B.
Tóm lại $x=10000003826$.
About TS. Nguyễn Thái Sơn
