TỐC ĐỘ X2
TỐC ĐỘ X2
TỐC ĐỘ X2

CHUYÊN ĐỀ ÔN THI

Tìm dư của phép chia số a^(b^c) cho số nguyên tố p.

MụclụcTHCS

abc mod p{\Large a^{b^c}} \ \text{mod}\ pabc mod p{\Large a^{b^c}} \ \text{mod}\BÀI TOÁN

Tìm dư của phép chia số 2642026\Large 26^{4^{2026}} cho 20272027.


HƯỚNG DẪN GIẢI

Ta xét các số nguyên dương a,b,c,pa, b, c, p   với pp là số nguyên tố, aa không chia hết cho pp  và bài toán abc mod p{\Large a^{b^c}} \ \text{mod}\ p.

  1. p p là số nguyên tố nên theo định lý Euler ap11(mod p)a^{p-1} \equiv 1 \quad (\text{mod}\ p) . Do đó ta sẽ tối giản mũ bcb^c bằng cách tìm dư dd của phép chia bcb^c cho p1p-1.
  2. Bài toán trở thành tìm dư của phép chia ada^d cho pp.

Bấm  w9nhập số 2026 rồi bấm  2 lần ta có:  . Vậy 2026=21+23+25+26+27+28+29+210.2026=2^1+2^3+2^5+2^6+2^7+2^8+2^9+2^{10}.

Do đó 

  (chỗ bị khuất là .IntA122026 )\text{Int}\dfrac{A1^2}{2026}\ )

Đưa con trỏ tới B5, chuẩn bị tính tích luỹc tiến  (chỗ bị khuất là A1A3A52026 )\dfrac{ A1A3A5}{2026}\ ).

Đưa con trỏ tới B6 tính tích luỹ tiến    (Chỗ bị khuất là IntB5A62026 )\text{Int} \dfrac{B5A6 }{2026}\ )  .

Vậy .

Ta có: .

  |  
. Do đó:  

Kết luận: dư của phép chia số 2642026 cho 2027 là 993993.