若a与n互质，则a^φ(n) mod n 同余 1
证明:假设1~n中所有与n互质的数有：a1，a2......aφ(n)，由于ai与n互质，并且a和n互质，所以aa1，aa2......aaφ(n)也都与n互质，并且可证他们两两不同，使用反证法证明：假设相同ij，则aai同余aaj化简之后得到a(ai-aj)modn同余0，并且由于a和n互质所以a是可以消掉的,所以得到ai同余aj，所以矛盾，假设不成立。证明完毕，得到性质：之前得到的两组数是同一组数只不过顺序可能有所改变，所以可知乘积是相同的，即a^φ(n)(a1…aφ(n)) 与(a1…aφ(n))modn同余，由于(a1…aφ(n))与n互质，所以可以消掉等式两边的(a1…aφ(n))得到a^φ(n) mod n同余 1，证毕

ps：费马小定理：欧拉定理的特殊情况，当n是质数的时候欧拉定理简化成a^p-1 mod p 同余 1