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
Giải hệ 2 phương trình đồng dư khi các mod không nguyên tố cùng nhau
- 02/09/2024
- 474 lượt xem
| Lời nói đầu. Từ một bài toán không phức tạp trong kỳ thi HSG MTCT cấp TP HCM chủ yếu dùng tính năng lập bảng, nhiều quận huyện đã cho những bài toán về hệ phương trình đồng dư mà không thể truy xuất kết quả từ bảng. Một số thầy cô phụ trách đội tuyển đã dựa vào Định lý phần dư Trung Hoa để giải, đi đầu là cô Dương Hoàng Bích Thuận đã giới thiệu giải pháp tìm nghịch đảo mô-đu-lô của một số a theo mod b. Sau khi đã biết cách giải hệ phương trình đồng dư bằng định lý phần dư Trung Hoa, phát sinh ra bài toán hệ phương trình đồng dư mà các mod không nguyên tố cùng nhau. Việc soạn ra các bài toán này không khó: Lấy một số nguyên cực lớn chia cho ba số nguyên rất lớn để biết dư, sau đó yêu cầu học sinh tìm số nguyên cực lớn đó. Ra bài toán thì dễ nhưng giải bài toán không dễ. Thầy Nhut Nguyen đã có nhiều sáng kiến để giải bài toán này. Dựa vào sự trao đối của các thầy cô phụ trách đội tuyển trao đổi trên diễn đàn, Thầy Sơn tổng kết lại thành công thức dưới đây và xin lưu ý nội dung này không nên dạy cho HS lớp 9 dù là HSG MTCT để đi thi cấp quận, vì với các thầy cô phụ trách đội tuyển không phải ai cũng giải được dễ dàng. Bài này được xem một tài liệu tham khảo nâng cao trình độ chuyên môn cho GV giảng dạy số học ở bậc THCS các lớp bồi dưỡng HSG MTCT. |
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: |
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)}$ và $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$$
Bài toán:
| Giải hệ phương trình $$\left\lbrace\begin{array}{l}x \equiv 45\qquad \text{mod} \ 1358\\ x \equiv 117\quad \ \ \text{mod}\ 3518\\ x \equiv 4375\quad \text{mod}\ 15381\\ \end{array} \right. $$ |
Hệ phương trình $⇔ \left\lbrace\begin{array}{l}
x\equiv 1512857\quad \text{mod}\ 2388722\\
x \equiv 4375\qquad\ \ \text{mod}\ 5381
\end{array} \right. $
Vì $\text{gcd}(2388722,5381)=1 $ nên theo định lý phần dư Trung Hoa, hệ phương trình có nghiệm duy nhất $$x=1512857.5381z_1+4375.2388722.z_2\quad \text{mod}\ 12853713082$$
với $z_1$ là nghịch đảo của 5381 mô-đu-lô 2388722 và $z_2$ là nghịch đảo của 2388722 mô-đu-lô 5381.
Thực hiện phép tính: $1512857.5381(2388722-837673)+4375.2388722.1887$ lưu vào A và $12853713082$ lưu vào B. dư của phép chia A cho B là:
Vậy $x \equiv 999998653+12853713082k \quad (k \in \mathbb{Z})$.
 |
About TS. Nguyễn Thái Sơn
