Question

一道取模运算的题目求解，另外问一下解题方法

2^100 mod 97

Answer 1

用费马定理
97 是素数, (100,97)=1, 所以有
2^(97-1) = 1 mod97
即 2^96 = 1 mod97

所以有 2^100 = 2^96 2^4 = 2^4 = 16 mod97

Answer 2

数学上要算出97的阶，发现2^48%97 = 1所以2 ^100 ≡ 2^(100 - 48*2) (mod 97)
余数是2^4=16
程序上用幂取模算法来做：一下c程序
#include<stdio.h>
int f(int a,int b)
{
if(b==1)return a;
int t=f(a,b/2);
if(b%2==0)
return t*t%97;
else return t*t*a%97;
}
int main()
{
printf("%d",f(2,100));
}

Answer 3

2^100 mod 97
≡(2^7)^14*2^2 mod 97
≡4*31^14 mod 97
≡$*(31*31)^7 ≡4*(-9)^7 mod 97
≡-36*81^3 ≡36*16^3 mod 97
≡(16*6)^2*16 mod 97
≡16