本文讲如何通过找指数循环节对高次幂进行降幂，来求解高次幂取模问题。

一. 概述

假如现在有这么一个问题

给定三个正整数a，b和m，且a与m互素，求a^b mod m的值，这里b可能特别大，例如b∈[1, 10^100000]。

因为a与m互素，根据欧拉定理，可知有

那么通过欧拉定理直接对b进行处理，使其变小，即

特别地，当m为素数，欧拉定理衍变为费马小定理，等式变为

结合快速幂取模算法，这个问题就完美解决了。

但如果a与m不互素呢，这时候又应该怎么处理？这就是接下来要讲的一个重要的降幂公式。

二. 降幂公式及证明

首先来看这个降幂公式的内容，如下

设a，b和m为正整数，那么有

通过这个降幂公式，就能对a与m不互素的情况也能处理，这个降幂公式非常重要，下面来证明一下

考虑如下序列

上述序列一共m+1个数，而一个数模m最多有m个不同的结果，根据鸽巢原理m以内必定会存在最小的两个数r和s，它们对m的取模结果相等，即有

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。