Bài toán tổng quát về hệ phương trình đồng dư
Đề bài: Tìm số có 14 chữ số, biết rằng chia 7741 dư 2017, chia 2017 dư 2013, chia 2013 dư 2011.
Bài giải
Vì các số 7741,2017,20137741,2017,2013 đôi một nguyên tố cùng nhau, nên ta đi giải hệ phương trình đồng dư sau:
\(\begin{cases} x\equiv2017 & \text{mod}\,7741\\ x\equiv2013 & \text{mod}\,2017\\ x\equiv2011 & \text{mod}\,2013 \end{cases}\,\,\,(I)\)
Thì hệ có nghiệm duy nhất theo modulo M=7741×2017×2013 là:
\(x\equiv a_1.M_1.y_1+a_2.M_2.y_2+a_3.M_3.y_3\)
Trong đó \(a_1=2017;\,a_2=2013;\,a_3=2011\); \(M_1=2017\times 2013; M_2=7741 \times 2013; M_3=7741 \times 2017\);
\(y_1=(M_1)^{-1}\,\,\text{mod }m_1; y_2=(M_2)^{-1}\,\,\text{mod }m_2; y_3=(M_3)^{-1}\,\,\text{mod }m_3\)
Vấn đề ta đi tìm nghịch đảo bằng cách áp dụng thuật toán Euclid:
+ Tìm nghịch đảo của 3937 theo modulo 7741: 7450
+ Tìm nghịch đảo 1308 theo modulo 2017: 165
+ Tìm nghịch đảo 769 theo modulo 2013: 1924
Quá trình tìm nghịch đảo theo modulo:
Vậy nghiệm cần tìm là:
\(x=2017\times 2017 \times 2013 \times 7450+2013 \times 7741 \times 2013 \times 165 +\)
\(+ 2011 \times 7741 \times 2017 \times 1924 = 126598780950343\)
Nghiệm \(x\) cần tìm: \(x \equiv 29483295796 + 31430170761a\) và từ đây, dựa theo điều kiện đề bài để tìm số \(a\) nguyên cho phù hợp.
Kết luận số cần tìm: 99977426315776.