Giải hệ phương trình đồng dư bằng định lý phần dư Trung Hoa

Định lý phần dư Trung Hoa (hay còn gọi là “bài toán Hàn Tín điểm binh”).

Xét hệ phương trình:
$$\left\{
\begin{array}{l} x \equiv a_1 \quad (\kern-.2em\mod m_1) \\
x \equiv a_2 \quad (\kern-.2em\mod m_2) \\
x \equiv a_3 \quad (\kern-.2em \mod m_3) \\
\end{array}\right.$$ trong đó $m_1, m_2, m_3$ đôi một nguyên tố cùng nhau.

 

Hệ phương trình đồng dư nói trên có nghiệm duy nhất là: $x=a_1y_1z_1+a_2y_2z_2+a_3y_3z_3\quad (\kern-.5em\mod m)$

với $m=m_1.m_2.m_3$, $y_1=\dfrac{m}{m_1}$, $y_2=\dfrac{m}{m_2}$, $y_3=\dfrac{m}{m_3}$ và $z_i$ là nghịch đảo của $y_i$ theo mô-đu-lô $m_i$, nghĩa là $z_i.y_i \equiv 1\ (\kern-.5em\mod m_i)$ ($i=1,2,3$).

 

Cách đây hai năm, trên BITEXEDU chúng tôi đã trình bày cách dùng bảng tính để tìm nghịch đảo mô-đu-lô. Hôm nay chúng tôi nhắc lại, theo hướng “dễ nhớ hơn”, bằng cách nói trước thực hành sau.
 

Giả sử ta muốn tìm nghịch đảo theo mô-đu-lô $m_1=7741$ của số $y_1=$3937 , ta nhập $m_1, y_1, 0, 1$ lần lượt vào $A_1, B_1, C_1, D_1$. bt1aa
 

Tiếp theo ta dời số liệu từ cột B “chéo xuống” cột A, dời số liệu từ cột D “chéo xuống” cột C như minh hoạ bt1a
 

Trên cột B từ $B_2:B_{20}$ ta tìm dư của phép chia cột A cho cột B theo dòng tương ứng. Ví dụ tại dòng 2 phép tính là:$A_1-B_1$.Int($A_1\div B_1$).

Trên cột D từ $D_2:D_{20}$ ta thực hiện phép tính $C-D$.Int($A\div B$) (dòng tương ứng), ví dụ dòng 2 phép tính là: $C_1-D_1$.Int($A_1\div B_1$).
 

Quan sát kết quả, ở dòng nào mà cột B là $1$ thì tại dòng đó, cột D sẽ là nghịch đảo cần tìm nếu nó là số dương. Nếu nó là số âm ta cộng cho $k$ lần $m_1$ (với $k$ nhỏ nhất mà kết quả là dương), giá trị dương này sẽ là nghịch đảo cần tìm.

 

Bài luyện tập – bài thi HSG MTCT THCS
 

Tìm số tự nhiên $x$ lớn nhất có 14 chữ số, biết $x$ chia cho $7741$ dư $2017$, chia cho $2017$ dư $2013$ và chia cho $2013$ dư $2011$.

 

Xét hệ phương trình đồng dư

$$\left\lbrace\begin{array}{llll}
x & \equiv & 2017 & (\text{mod} \ 7741)& \\
x & \equiv & 2013 & (\text{mod} \ 2017)& \\
x & \equiv & 2011 & (\text{mod} \ 2013)
\end{array} \right.
$$
fb5a
Vì $7741, 2017,2013$ nguyên tố cùng nhau nên ta có thể sử dụng Định lý Phần dư Trung Hoa. Khi đó nghiệm duy nhất của hệ phương trình là $$x=2017.2017.2013z_1+2013.2013.7741z_2+2011.7741.2017z_3\quad (\kern-.51em\mod 2017.2013.2011)\qquad (*)$$
trong đó $z_1, z_2, z_3$ lần lượt là nghịch đảo của $2017.2013$ theo mô-đu-lô $7741$,của $2013.7741$ theo mô-đu-lô $2017$ và của $7741.2017$ theo mô-đu-lô $2013$.
 
Bây giờ ta đi tìm $z_1$ sau đó tuỳ biến sẽ có $z_2$ và $z_3$.
 

Lần lượt nhập $7741, 2017\times 2013, 0 ,1$ lên dòng 1 như hình: fb6a

Dời “chéo xuống” số liệu từ cột B sang cột A và từ cột D sang cột C (chọn phạm vi 20 dòng) bằng cách đưa con trỏ tới $B_2$ điền công thức và đưa con trỏ tới $C_2$ điền công thức như hình:
 
fb6bc
 

Đưa con trỏ tới $B_2$ điền công thức, phạm vi $B_2:B_{20}$ để tìm dư của phép chia $A_i$ cho $B_i\quad (i=1,2,\dots, 20)$, bỏ qua thông báo lỗi (chia cho $0$) như hình:
 

fb6b 1
 

Đưa con trỏ tới $D_2$ điền công thức, phạm vi $D_2:D_{20}$ thực hiện phép tính như trong hình, bỏ qua thông báo lỗi (chia cho $0$):
 
fb6c 1
 
Duyệt cột $B$ thấy $B_{10}=1$ mà $D_{10}=-291<0$ nên $z_1=-291+7741=7450$. fb6d

 

Bây giờ ta tuỳ biến giá trị nhập vào để có $z_2$ và $z_3$. Đưa con trỏ vào $A_1$ nhập $2017$, vào $B_1$ nhập $2013.7741$, bỏ qua thông báo lỗi (chia cho $0$) (hình bên trái), sau đó duyệt cột $B$ thấy $B_9=1$ nên $z_2=D_9=165$.
fb6e

Lại đưa con trỏ vào $A_1$ nhập $2013$, vào $B_1$ nhập $7741.2017$, bỏ qua thông báo lỗi (chia cho $0$) (hình bên trái), sau đó duyệt cột $B$ thấy $B_{12}=1$ mà $D_{12}=-89<0$ nên $z_2=-89+2013=1924$.
fb6f
 
Đem $z_1, z_2, z_3$ thay vào công thức (*) ở trên, ta có:
$$x = a_1y_1z_1+a_2y_2z_2+a_3y_3z_3 + k m_1m_2m_3 = 126598780950343+31430170761k, k \in \mathbb{Z}$$
Vì $x$ lớn nhất và có 14 chữ số nên $k$ lớn nhất thoả $k<$ fb6g. Vậy $k=-847$. Do đó số cần tìm là $$x=126598780950343+31430170761\times (-847)=99977426315776$$
 
 

Câu 1: Kỳ thi HSG MTCT TP HCM 17/01/2016
hsghcm1a

 

Chia sẻ

About TS. Nguyễn Thái Sơn

TS. Nguyễn Thái Sơn
Nguyên trưởng Khoa Toán-Tin học ĐHSP TP HCM (1999-2009). /n Nguyên Giám đốc- Tổng biên tập NXB ĐHSP TP HCM (2009-2011). /n Nguyên Tổng thư ký Hội Toán học TP HCM (2008-2013). /n Giảng viên thỉnh giảng ĐHSP TP HCM.

Bài Viết Tương Tự

Trao đổi chuyên môn: Phần nguyên của số $(2+\sqrt{3})^{32}$

Bài viết này nhằm trao đổi chuyên môn với các thầy cô phụ trách đội …

×

Sai số! tác hại to lớn của việc sử dụng máy tính Casio giả và cách phòng tránh Chi tiết