a^13=a(mod78),为什么,证明a^13=a(mod78),a为整数

Question

a^13=a(mod 78),为什么,
证明a^13=a(mod 78),a 为整数

Answer 1

证明：
a^13-a=a(a^12-1).
若gcd(a,13)=1,则由费马小定理可知13|a^12-1,于是
13|a(a^12-1)；
若gcd(a,13)≠1,则必有13|a,于是也有13|a(a^12-1)；
综上可知,对任意整数a,都有13|a(a^12-1)；
同理,2|a(a^12-1)；3|a(a^12-1)；
又因为2,3,13两两互质,从而2*3*13|a(a^12-1),即：
78|a^13-a,故a^13=a(mod 78),证毕!