|
这是数论中的欧拉定理 φ(n)是一个函数即小于n与n互素的数的个数证明首先证明下面这个命题： 对于集合Zn={x1,x2,...,xφ(n)},其中xi(i=1,2,…φ(n))是不大于n且与n互素的数，即n的一个化简剩余系，或称简系，或称缩系)，考虑集合S = {a*x1(mod n),a*x2(mod n),...,a*xφ(n)(mod n)} 则S = Zn 1) 由于a,n互质，xi也与n互质，则a*xi也一定于n互质，因此 任意xi，a*xi(mod n) 必然是Zn的一个元素 2) 对于Zn中两个元素xi和xj，如果xi ≠ xj 则a*xi(mod n) ≠ a*xj(mod n)，这个由a、n互质和 |
