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
Sử dụng bảng tính tìm nghịch đảo modulo $a$ của số $b$.
- 11/10/2022
- 1,148 lượt xem
| Định nghĩa: Nghịch đảo modulo $a$ của số $b$ là một số $c$ sao cho $bc\equiv 1\ \text{mod}\ a$.
Ví dụ: 8 là nghịch đảo của 7 theo modulo 11 vì $8\times 7 \equiv 1\ \text{mod}\ 11$.
Nếu $a$ và $b$ là nhứng số rất lớn ta không thể nhẩm tính như trên. Khi đó ta sẽ cần dùng đến một thuật toán, được gọi là thuật toán Euclide mở rộng. Trong bài viết này chúng tôi sử dụng bảng tính để chạy thuật toán Euclide mở rộng. |
Bài toán: Hãy tìm nghịch đảo của $3937$ theo modulo $7741$.
Bước 1: Mở một bảng tính mới nhập $a=7741$, $b=3937$, $C=0, D=1$ lần lượt vào A1,B1, C1 và D1.
Bước 2: Để con trỏ ở đâu cũng được, nhưng để thuận tiện đưa vào A2, ban hành công thức thông qua Tools-Fill Formula như sau:
Bước 3: Để con trỏ ở B2, dùng Tools – Fill Formula
Nếu gặp một thông báo lỗi 
, bấm BACK để bỏ qua.
Bước 4: Để con trỏ ở C2, dùng Tools – Fill Formula
bỏ qua thông báo lỗi.
Bước 5: Để con trỏ ở D2, dùng Tools – Fill Formula
bỏ qua thông báo lỗi. Đưa con trỏ dọc theo cột D khi nào thấy cột B tương ứng là số 1 (đầu tiên) thì vị trí cột và dòng đó chính là nghịch đảo của 3937 theo modulo 7741. Ta thấy đó là số $-291$.
| Lưu ý: Sau khi xây dựng thuật toán thành công ta chỉ cần cập nhật số ở A1 và B1 ta sẽ có nghịch đảo modulo của cặp số khác. Và do đó để giải hệ 3 phương trình đồng dư (Định lý phần dư Trung Hoa), ta có thể tìm nhanh 3 nghịch đảo modulo của ba cặp số trong hệ 3 phương trình đồng dư. |
| Nhận xét:
1. Lần báo Math Error đầu tiên (khi tìm dư của phép chia gặp phép chia cho $0$) là dấu hiệu cho biết thuật toán đã dừng trước lần thứ 20 và tìm được nghịch đảo moodulo.
2. Các lần báo Math Error tiếp theo (cũng là khi gặp phép chia cho $0$) không ảnh hưởng gì tới kết quả vì máy tính vẫn chạy. |
About TS. Nguyễn Thái Sơn
