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
Tìm dư của phép chia $a^{b^c}$ cho $p$ ($p$ là số nguyên tố)
- 1 ngày trước
- 193 lượt xem
| Bài toán. Tìm dư của phép chia $a^{b^c}$ cho $p$ ($a, b, c, p \in \mathbb{N^*}, p$ là số nguyên tố) |
Cách giải.
Bước 1: Vì $p$ là số nguyên tố nên $\text{GCD}(a,p)=1$ và theo định lý Euler ta có $a^{p-1} \equiv 1 \quad (\text{mod}\ p)$.
Bước 2: Tối giản $b^c$ bằng cách tìm dư của phép chia $b^c$ cho $p-1$. Nếu $c \geqslant 2025$ ta phân tích $b^c=b^{2025}\cdot b^{c-2025}$ và lưu ý $2025=3^4\times 5^2$.
Bước 3: Gọi $d$ là dư của phép chia $b^c$ cho $p-1$. Bài toán trở thành tìm dư của phép chia $a^d$ cho $p$.
Bài giải.
Vì $2027$ là số nguyên tố nên $26^{2026} \equiv 1 \quad (\text{mod}\ 2027)$. Do đó $26^{4^{2026}}=\underbrace{\ \quad (26^{2026})^q\quad \ }_{\equiv 1 (\text{mod}\ 2027)}.26^r$ ($q$ và $r$ là thương và dư của phép chia số $4^{2026}$ cho $2026$. Chú ý: “lấy mũ ($4^{2026}$) chia mũ ($2026$)”. )
Ta tìm $r$ là dư của phép chia số $4^{2026}$ cho $2026$ (mũ chia mũ).
$4^{2026}=4^{2025}.4=\underbrace{4^{3^4\times 5^2}}_{\equiv 4 \ (\text{mod}\ 2026)}.4 \equiv 16 \quad (\text{mod}\ 2026)$.
Tiếp tục tìm dư của phép chia $26^{16}$ cho $2027$ (mũ đã giảm đi rất nhiều).
Tính toán như đã biết $26^{16} =(26^4)^4 \equiv 663 \quad (\text{mod}\ 2027)$ 
.
Vậy dư của phép chia $26^{4^{2026}}$ cho $2027$ là $663$.
About TS. Nguyễn Thái Sơn
