求5^(5^31)模17的余数的方法咨询

嗨，你已经迈出了关键的第一步，费马小定理的应用完全正确！接下来我们只需要把这个大指数拆解简化就行，我一步步给你讲清楚：

• 首先，回顾你用到的费马小定理：因为17是质数，且5和17互质，所以 5^16 ≡ 1 (mod 17)。这意味着对于任何正整数k，5^k ≡ 5^(k mod 16) (mod 17)——毕竟每16次幂就会循环回到1，所以我们只需要求出指数 $5^{31}$ 模16的结果，就能简化原式。
• 接下来计算 $5^{31} \pmod{16}$：
  • 先找5的幂在模16下的循环规律：$5^2 = 25 ≡ 25-16 = 9 \pmod{16}$，进一步计算 $5^4 = (5²⁾2 = 9^2 = 81 ≡ 81-5*16 = 1 \pmod{16}$。发现了吗？5的4次幂模16等于1，循环周期是4！
  • 把31拆成 $47 + 3$，那么 $5^{31} = 5^{47 + 3} = (5⁴⁾7 * 5^3$。代入上面的结果，就是 $1^7 * (5^2 * 5) = 1*(95) = 45$，再计算45模16：$45-216=13$，所以 $5^{31} ≡13 \pmod{16}$。
• 现在回到原式，$5^{(5{31})} ≡5^{13} \pmod{17}$，接下来计算这个值：
  • 我们可以拆解幂次来简化计算：
    • $5^2 =25 ≡25-17=8 \pmod{17}$
    • $5⁴⁼⁽⁵2)²⁼⁸2=64≡64-3*17=64-51=13 \pmod{17}$
    • $5⁸⁼⁽⁵4)²⁼¹³2=169≡169-9*17=169-153=16≡-1 \pmod{17}$
  • 把5^13拆成 $5^8 *5^4 5^1$，代入数值就是 $(-1)135=-65$，再计算-65模17：$174=68$，$-65+68=3$，所以 $5^{13}≡3 \pmod{17}$。

最终，$5^{(5{31})}$ 除以17的余数是3。

备注：内容来源于stack exchange，提问作者user1051059