已知P是大于5的素数,求p^2除以30的余数

题目

已知P是大于5的素数,求p^2除以30的余数

答案

与30互质(互素)的数,包括了所有大于5的素数.
对于任意的大于5的素数p,
p mod 30 =±(1,7,11,13)
于是 pp mod 30=(1,49,121,169)=(1,19,1,19)=(1,19)
以上的简便写法,有待形成一规范,但意义很明白.