>>273
(a,n)=1 のとき mod n で異なる整数は
a_1 , a_2 , ・・・ , a_Φ(n) のΦ(n) 個。
{a_1 , a_2 , ・・・ , a_Φ(n)}
と
{a*a_1 , a*a_2 , ・・・ , a*a_Φ(n)}
は集合として一致する。全部かけ合わせて
a^Φ(n) * (a_1*a_2*・・・*a_Φ(n)) ≡ (a_1*a_2*・・・*a_Φ(n))
a_1*a_2*・・・*a_Φ(n) は n と互いに素だから両辺をこれで割って
a^Φ(n) ≡ 1