Giải hệ 2 phương trình đồng dư khi các mod không nguyên tố cùng nhau

Bài toán: Cho hệ phương trình $$\left\lbrace\begin{array}{l}x \equiv a_1\quad (\text{mod}\ m_1)\\ x \equiv a_2\quad (\text{mod}\ m_2)\end{array} \right. $$ Nếu $m_1, m_2$ nguyên tố cùng nhau, nghĩa là $\text{gcd} (m_1,m_2)=1$ thì hệ phương trình có nghiệm duy nhất: $$x=a_1m_2z_2+a_2m_1z_1+km_1m_2\quad (k \in \mathbb{Z})$$ trong đó $z_2$ là nghich đảo của $m_2$ theo mô-đu-lô $m_1$ và $z_1$ là nghịch đảo của $m_1$ theo mô-đu-lô $m_2$.

Bây giờ ta xét khi $m_1, m_2$ không nguyên tố cùng nhau. Trong trường hợp này hệ phương trình có nghiệm khi và chỉ khi $a_1\equiv a_2 \quad \text{mod}\ \text{gcd} (m_1,m_2) $. (nghĩa là $a_2-a_1$ chia hết cho $\text{gcd}(m_1,m_2)$).

Khi đó nghiệm duy nhất của hệ phương trình là $$x \equiv c\quad \text{mod}\ \text{lcm} (m_1,m_2)$$ với $c$ được xác định như sau:

• Đặt $M_1=\dfrac{m_1}{\text{gcd}(m_1,m_2)}$,
• $M_2=\dfrac{m_2}{\text{gcd}(m_1,m_2)}$
• $z_3$ là nghịch đảo của $M_1$ theo mô-đu-lô $M_2$.
• Khi đó $$c=a_1+m_1.c'$$ với $c' \equiv \dfrac{a_2-a_1}{\text{gcd} (m_1,m_2)}.z_3\quad (\text{mod}\ M_2)$.

Bằng cách sử dụng phép chia có dư ta chọn $c'$ phù hợp với yêu cầu bài toán để tính được $c$.

Bài tập áp dụng: Giải hệ phương trình $\left\lbrace\begin{array}{l}x\equiv 45\quad \ \ (\text{mod} \ 1358)\\ x\equiv 117\quad (\text{mod} \ 3518)\end{array} \right. $

Ta có:

• $\text{gcd}(1358,3518) =2, \text{lcm}(1358,3518) =2388722$.
• $M_1=\dfrac{1358}{\text{gcd}(1358,3518)}=679, M_2=\dfrac{3518}{\text{gcd}(1358,3518)}=1759,$
• $\dfrac{a_2-a_1}{\text{gcd} (m_1,m_2)}=36$.
• Dùng thuật toán tìm nghịch đảo mô-đu-lô trên bảng tính ta có: $z_3=715$.

Vậy nghiệm của hệ phương trình là $$x\equiv 1512857\quad (\text{mod}\ 2388722)$$