幂同余定理及其应用
吴敏金mjwu1940@
由同余式的性质，可推出
[幂同余定理]
设同余式a==b (mod m)，那么对于任意的正整数n,
a^n==b^n (mod m).。

（^n表示n次方，==表示同余）证明：
由同余式的性质，如果a==b (mod m)，c==d (mod m)，则a*c==b*d (mod m)。

取c=a, d=b，作n次乘法即得结论。

证毕
幂同余定理可应用于幂同余方程求解：
对于给定的m,n，已知a，求a^n==x (mod m)，(0<=x<m)。

实例如下。

1，求3^2015除以26的余数？
解：由3^3=27==1 (mod 26)，
3^2015=(3^3)^671*3^2
==1^671*9==9 (mod 26).
所以，3^2015除以26的余数为9。

,2，求13^2015除以170的余数？
解：由13^2=169==-1 (mod 170)，
13^2015=(13^2)^1007*13
==(-1)^1007*13==-13==155 (mod 168)
所以，13^2015除以170的余数为155。

由上面2例可见，利用幂同余定理
比直接计算3^2015，13^2015方便得多了。

下面示例，给出当a>m时的求解方法。

3，求23^5555除以7的余数？
解：由23==2 (mod 7), 及8==1 (mod7)
23^5555==2^5555==(2^3)^1851*4==1^1851*4==4 (mod 7)
所以，23^5555除以7的余数为4。

对于另一类幂同余方程：对于给定的m,n，已知b, 求x^n==b (mod m)。

较为复杂，另文讨论。