>>856
フェルマーの小定理。 a と p は互いに素という条件が必要。

a , 2a , 3a , ・・・ , (p-1)a
という p-1 個の整数において i , j を1≦i＜j≦p-1 を満たす整数とすると
ja - ia = (j-i)a は p で割り切れないので 上の整数のうちどの2つを選んでも
p で割った余りは異なる。また、上のp-1 個の整数を p で割った余りは
1 から p-1 までの値をとりうるので、1 から p-1 まですべてそろっている。
よってこれらを全部かけ合わせたとき
a^(p-1) * (p-1)! ≡ (p-1)!　(mod p , 以下同)
が成り立つが　(p-1)! と p は互いに素なので、両辺をこれで割ると
a^(p-1) ≡ 1　となる。