Thuật toán tìm nghịch đảo mô-đu-lô trên MTCT

Trong định lý phần dư Trung Hoa với các số đưa vào khá lớn, ta không dùng chức năng lập bảng mà phải dùng nghịch đảo của một số theo mô-đu-lô.

Ta quy định các số trong bài này là các sô tự nhiên.

Đinh nghĩa: Số $z$ được gọi là nghich đảo của số $y$ theo mô-đu-lô $A$ nếu $yz\equiv 1\ \text{mod}\ A$.

 

Thuật toán trên máy tính Casio fx-580VN X như sau:

thuattoan 1

Ví dụ: Tìm nghịch đảo của 3937 theo modulo 7741.

Trước hết ta lấy $7741$ lưu vào A, $3937$ lưu vào y ndm2Sau đó thực hiện phép chia có dư A cho y trên MTCT ndm
Tiếp theo viết thuật toán lên màn hình, bấm CALC máy tính sẽ hỏi A ta bấm mũi tên xuống (tức là chấp nhận đề nghị), hỏi y ta chấp nhận, hỏi C ta nhập 0, hỏi D ta nhập 1, hỏi E ta chấp nhận, hỏi F ta chấp nhận.Cuối cùng nhấn Enter (=) nhiều lần cho đến khi vào thấy dư R=1 ndm3 thì dừng lại, nhấn enter (=) sẽ thấy $z$.

 

Vậy nghịch đảo của 3937 theo modulo 7741 là $-291$.

 

 

Áp dụng – 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 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.
$$

Nghiệm của hệ phương trình đồng dư là
$$x=a_1y_1z_1+a_2y_2z_2+a_3y_3z_3+(7741\times 2017\times 2013)k$$
trong đó
 

$a_1=2017, y_1=2017\times 2013$ndm1a

 
$a_2=2013, y_2=7741\times 2013$ ndm1b

 
$a_3=2011, y_3=7741\times 2017$ ndm1c

 

Tìm các nghịch đảo mô-đu-lô như trên cho $1308$ và $769$ ta có $z_2=163$ và $z_3=-89$

$$x \equiv a_1y_1z_1+a_2y_2z_2+a_3y_3z_3 + k n_1n_2n_3 \equiv 126598780950343+31430170761k, k \in \mathbb{Z}$$

Để $x$ lớn nhất có 14 chữ số, số nguyên $k$ lớn nhất thoả điều kiện $k \leqslant\ $ ddm1f. Vậy $k=-847$

Vậy số cần tìm là th $= 99.977.426.315.776$

Chia sẻ

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

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

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

MTCT trợ giúp giải hệ phương trình khó (THCS) – Bài 1

Đề thi vào lớp 10 SGD và ĐT Nghệ An năm học 2021-2022   Điều …

×

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