Tìm dư của phép chia $a^n$ cho $b$ với $n$ và $b$ tuỳ ý.

Đặt vấn đề. Chúng ta đã trao đổi khá nhiều khi $n$ và $b$ có liên quan đến năm thi, ví dụ $2025, 2026, \dots ,2029$. Tuy nhiên nếu $n$ và $b$ là các số tự nhiên bất kỳ chúung ta sẽ đưa ra cách giải thống nhất cho trường hợp tổng quá này mà không dùng thuật toán luỹ thưuà nhanh (khó nhớ). Tất nhiên cách làm mới này cũng áp dụng cho các bài toán quen thuộc.

 

Bài toán. Tìm dư của phép chia số $1234^{5678}$ cho $91011$.

 

nut baigiaimoi

.
 

 

baivietmoi1a baivietmoi1b Bấm FORMAT 2 lần baivietmoi1c.
 

Vậy $5678=2^1+2^2+2^3+2^5+2^9+2^{10}+2^{12}$ (đếm từ bên phải dòng dưới đếm lên, chú ý vị trí của số $1$, vị trí đầu tiên là vị trí $0$). Do đó: $$\boldsymbol{1234^{5678}=1234^{2^1}\times 1234^{2^2}\times 1234^{2^3}\times 1234^{2^5}\times 1234^{2^9}\times 1234^{2^{10}}\times 1234^{2^{12}}}$$
 

Gán số chia vào biến nhớ baivietmoi1d (là số chia $b$ chứ không cơ số $a$ của số bị chia).
 
Mở một bảng tính, tại $A_1$ nhập baivietmoi2a (tận dụng $A_1$ để tính $a^{2^1}$, nghĩa là nếu bắt đầu $2^m$ thì viết tại $A_m$).
 

Từ $A_2$ đến $A_{12}$ điền công thức: baivietmoi2b (công thức đầy đủ: $A_1^2-A \text{Int}(A_1^2\div A)$ ).
 
Như vậy cột $A$ sẽ chứa $1234^{2^m}\ (m=1,2,\dots , 12)$. Ta chỉ sử dụng các số hạng của tích nên ta sao chép $A_{\text{thích hợp} }$ vào cột $B$
 
baivietmoi2c baivietmoi2d baivietmoi2e
 
baivietmoi2f baivietmoi2g baivietmoi2h
 
baivietmoi2i.
 

Bắt đầu tích tích luỹ thiến, trước hết ta tính $B_1\times B_2 \quad (\text{mod}\ A) $ baivietmoi3a. công thức đầy đủ $B_1\times B_2-A \text{Int}(B_1\times B_2 \div A)$.
Sau đó điền công thức baivietmoi3b. Công thức đầy đủ $B_3\times C_2-A \text{Int}(B_3\times C_2 \div A)$.
 

Kết quả xuất hiện tại tích luỹ tiến cuối cùng: baivietmoi3c
 
Đối chiếu với XCAS (của ĐH Jospeh Fourier), Geobegra được nhượng quyền nhưng không tính được (do đầu tư lớn vào đồ thị).
 
baivietmoi
 
 

Chú ý: $n$ và $b$ bao nhiêu cũng được nhưng $a$ không nên quá lớn vì khi đó các phép tính $a$ luỹ thừa sẽ tràn bộ nhớ của máy tính cầm tay.

 

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ự

Tìm dư của phép chia số $(a+\sqrt{b})^n+(a-\sqrt{b})^n$ cho $2028$.

Bài toán. Ta tìm dư của phép chia số $(3+\sqrt{10})^{2020}+(3-\sqrt{10})^{2020}$ cho $2028$.     Đây …