Cách tìm nghịch đảo của số $a$ theo mô-đu-lô $m$.

Ta muốn tìm nghịch đảo của $a=19\times 23$ theo mô-đu-lô $m=17$.
 

Mở một bảng tính, nhập mod $(17)$ vào $A_1$ nhập số cần tìm nghịch đảo vào $A_2$.

Từ $A_2$ xuống dưới (đến kết quả cuối cùng là $1$) điền công thức để tìm dư của phép chia dòng dưới cho dòng trên: $A_1-A_2 \text{Int}\dfrac{A_1}{A_2}$, phạm vi phù hợp.

Tại $B_1$ nhập số $0$, $B_2$ nhập số $1$, từ $B_3$ trở xuống điền công thức $B_1-B_2 \text{Int}\dfrac{A_1}{A_2}$, phạm vi phù hợp.

Ứng với $n$ mà $A_n=1$ thì $B_n$ là nghịch đảo của $a$ theo mô-đu-lô $m$.
 
 

 

Chia sẻ

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

TS. Nguyễn Thái Sơn
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).

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

Thuật toán lũy thừa nhanh