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
Phương pháp lũy thừa nhanh để tìm dư của phép chia $a^n$ cho b.
- 14/07/2025
- 824 lượt xem
| Đặt vấn đề. Phương pháp lũy thừa nhanh có một ưu điểm đó là không cần phải chọn cách làm phù hợp như trong phương pháp hạ dần lũy thừa. Nó có thể xuất ra được kết quả với $a, b, n$ tùy ý (tùy ý nhưng trong phạm vi của kỳ thi). |
|
Mô tả Thuật toán bằng lời
|
1. Xác định số bước sẽ ra kết quả: $N=[\log_2n]$.
(Đối với học sinh lớp 9, các em tìm hiểu thêm $\log_2n$ là một số $N$ sao cho $2^N=n$, ví dụ $\log_28=3$ vì $2^3=8$.) Nếu $\log_2n$ là một số thập phân (kết quả thực hiện trên máy tính) thì ta lấy $N$ là phần nguyên (số đứng trước dấu phẩy thập phân.)
2. Ta lần lượt tính $a^2, a^4, a^8, a^{16}, a^{32}, \dots , a^{2N}$ (số sau là bình số trước, số cuối cùng là $a^{2N}$).
3. Mỗi số trong các lũy thừa nói trên đi với trọng số.
Trọng số thứ nhất là $1$ nếu $a$ chẵn và bằng $a$ nếu $a$ lẻ.
Trọng số thứ hai bảo lưu nếu $\left[\dfrac{a}{2}\right]$ là chẵn và cập nhật nếu $\left[\dfrac{a}{2}\right]$ là lẻ.
Bảo lưu nghĩa là giữ lại trọng số ở trên (ở đây là trọng số thứ nhất), cập nhật nghĩa là lấy trọng số thứ nhất nhân cho $\underbrace{a^2\ (\text{mod}\ b )}_{\text{dư của phép chia}\ a^2\ \text{cho}\ b }$.
Trọng số thứ ba bảo lưu nếu $\left[\dfrac{a}{4}\right]$ là chẵn và cập nhật nếu $\left[\dfrac{a}{4}\right]$ là lẻ.
Nhắc lại, bảo lưu nghĩa là giữ lại trọng số ở trên (ở đây là trọng số thứ hai), cập nhật nghĩa là lấy trọng số thứ hai nhân cho $\underbrace{a^4\ (\text{mod}\ b )}_{\text{dư của phép chia}\ a^4\ \text{cho}\ b }$.
tiếp tục như vậy cho trọng số áp cuối.
Trọng số cuối cùng là do bảo lưu nếu $\left[\dfrac{a}{N}\right]$ là chẵn và do cập nhật nếu $\left[\dfrac{a}{N}\right]$ là lẻ.
Trọng số cuối cùng này chính là dư của phép chia $a^n$ cho $b$ mà ta phải tìm.
|
Chạy thuật toán lũy thừa nhanh trên máy tính Casio fx-880BTG
|
| Tìm dư của phép chia số $29^{376}$ cho $1975$. |
1. Mở một bảng tính 
nhập $376$ vào $\rm A_1$ 
.
2. Từ $\rm A_2$ đến $\rm A_9$ điền công thức: 
, kết quả ỏ cột A 
3. Đưa con trỏ lên $\rm B_1$ điền công thức 
kết quả: 
(số $0$ đóng vai trò bảo lưu, số $1$ đóng vai tròn cập nhật).
4. Đưa con trỏ lên $\rm D_1$ nhập phép tính $29^2$ (đúng ra phải nhập phép tính $\rm 29^2-1975\text{Int}(29^2/1975)$ để tìm dư của phép chia $29^2$ cho $1975$) nhưng vì $29^2=841$ chia cho $1975$ dư vẫn là $841$. Từ $\rm D_2$ đến $\rm D_9$ điền công thức: 
kết quả 
5. Đưa con trở tới $\rm C_1$ nhập $\rm 29^{B_1}$ 
, sau đó từ $\rm C_2$ tới $\rm C_9$ điền công thức:
, kết quả 
$246$ là dư của phép chia số $29^{376}$ cho $1975$.
Chạy thuật toán lũy thừa nhanh trên máy tính Casio fx-580VNX để tìm dư của phép chia số $29^{376}$ cho $1975$.
Bấm $\fbox{MENU} \ \fbox{1}$ mở màn hình Phép tính thường, nhập dòng lệnh như ở dưới:
Bấm $\fbox{CALC}$, khi máy tính hỏi:
$\bullet$ A ta nhập 
$\bullet$ C ta nhập 
, vì theo thuật toán $376$ là số chẵn (dư khi chia cho $2$ sẽ bằng $0$) nên $\rm 29^B=29^0=1$.
$\bullet$ D ta nhập 
, vì dư của phép chia $29^2$ cho $1975$ là $841$.
Bấm dấu 
liên tục cho đến khi thấy $\rm \fbox{A=1}$ thì bấm tới sẽ thấy $\rm C=246$
(chú ý không để bị lố trở lại không được).
. About TS. Nguyễn Thái Sơn
