Tìm dư của phép chia số a^(b^c) cho số nguyên tố p.
BÀI TOÁN
Tìm dư của phép chia số 2642026 cho 2027. |
HƯỚNG DẪN GIẢI
Ta xét các số nguyên dương a,b,c,p với p là số nguyên tố, a không chia hết cho p và bài toán abc mod p. - Vì p là số nguyên tố nên theo định lý Euler ap−1≡1(mod p) . Do đó ta sẽ tối giản mũ bc bằng cách tìm dư d của phép chia bc cho p−1.
- Bài toán trở thành tìm dư của phép chia ad cho p.
|
Bấm w9nhập số 2026 rồi bấm n 2 lần ta có:
. Vậy 2026=21+23+25+26+27+28+29+210.
Do đó
(chỗ bị khuất là .Int2026A12 ).Đưa con trỏ tới B5, chuẩn bị tính tích luỹc tiến
(chỗ bị khuất là 2026A1A3A5 ).Đưa con trỏ tới B6 tính tích luỹ tiến
(Chỗ bị khuất là Int2026B5A6 )
.
Vậy
.
Ta có: 2616=(264)4 .
2616≡663(mod 2027). Do đó:
Kết luận: dư của phép chia số 2642026 cho 2027 là 993.