欧拉定理(Euler Theorem)

组别：提高级
难度：7

欧拉定理（数论）： 在数论中，欧拉定理指出，如果两个整数a和n互质（即它们的最大公约数为1），则：a^ϕ(n)≡1(mod n)
其中，ϕ(n)是欧拉函数，表示小于n且与n互质的正整数个数。举个例子，假设 n=10， ϕ(10)=4，因为1, 3, 7, 9与10互质。若 a=33，因为3和10互质，根据欧拉定理，有 3⁴≡1 ( mod 10)。