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ư
- 13/10/2024
- 367 lượt xem
| Bài toán. Tìm số tự nhiên $x$ lớn nhất có 12 chữ số biết $x$ chia cho $2024, 26, 20, 18$ có số dư lần lượt là $1401, 1$, $9, 3$. |
Xét hệ phương trình $$\left\lbrace\begin{array}{ll}
x \equiv 3& \text{mod}\ 18\\
x \equiv 9& \text{mod}\ 20\\
x \equiv 1& \text{mod}\ 26\\
x \equiv 1401& \text{mod}\ 2024\end{array} \right. $$
| $$\left\lbrace\begin{array}{l}x \equiv a_1 \ \text{mod}\ m_1\\ x \equiv a_2 \ \text{mod}\ m_2\end{array} \right. ⇔ x \equiv a_1+m_1\times \dfrac{a_2-a_1}{\gcd(m_1, m_2)}\times z_3\quad \text{mod}\ \text{lcm}(m_1,m_2) $$ trong đó $z_3$ là nghịch đảo của $M_1=\dfrac{m_1}{\gcd(m_1,m_2)}$ theo mô-đu-lô $M_2=\dfrac{m_2}{\gcd(m_1,m_2)}$ |
.
Xét hệ phương trình $\left\lbrace\begin{array}{ll}
x \equiv 3& \text{mod}\ 18\\
x \equiv 9& \text{mod}\ 20\\
\end{array} \right. $
|
|
Xét hệ $\left\lbrace\begin{array}{ll}
x \equiv 1& \text{mod}\ 26\\
x \equiv 129& \text{mod}\ 180
\end{array} \right. $
| $\gcd(26,180)=2, \text{lcm}(26,180)=2340$. Đặt $M_1=\dfrac{26}{\gcd(26,180)}=$ $13$, $M_2=\dfrac{180}{\gcd(26,180)}=$ $90$, $z_3=7$ (nghịch đảo của $13$ theo mô-đu-lô $90$). $\left\lbrace\begin{array}{ll} x \equiv 1& \text{mod}\ 26\\ x \equiv 129& \text{mod}\ 180 \end{array} \right. ⇔ x \equiv 1+26\times \dfrac{129-1}{2} \times 7\quad \text{mod}\ 2340 ⇔ x \equiv 2289\ \text{mod}\ 2340 $. |
Xét hệ $\left\lbrace\begin{array}{ll}
x \equiv 1401& \text{mod}\ 2024\\
x \equiv 2289& \text{mod}\ 2340
\end{array} \right. $
| $\gcd(2024,2340)=4, \text{lcm}(2024,2340)=1184040$. Đặt $M_1=\dfrac{2024}{\gcd(2024,2340)}=$ $506$, $M_2=\dfrac{2340}{\gcd(2024,2340)}=$ $585$, $z_3=311$ (nghịch đảo của $506$ theo mô-đu-lô $585$). Vậy $x=1401+2024\times \dfrac{2289-1401}{4}\times 311+1184040k\quad (k \in \mathbb{Z}) ⇔ x=25689+1184040k\quad (k \in \mathbb{Z})$. |
Vì $x < 10^{12} ⇔ k < \dfrac{10^{12}-25689}{1184040}$ 
Vậy số $k$ lớn nhất thoả ycbt là $844566$.
Do đó số cần tìm $25689+1184040\times 844566=$ $999.999.952.329$
About TS. Nguyễn Thái Sơn
