公式在a和p互质的情况下

a ^(p-1) % p = 1;
首先
求(a ^ b) % p
假设 b = k(p-1) + c
那么原式等于 a ^ (k (p-1) + c ) % p = ( (a ^ k(p-1)  ) * (a ^ c)  ) %p
又因为 ( a^(p-1) ) ^k   %p = 1 所以 a^( k(p-1) + c )  同余 a ^ c (modp)
所以要求a ^ b (modp) 就相当于求 a^ (b %(p-1))