证明：若（a,561）=1,则a的560次幂与模561对于1同余

Question

证明：若（a,561）=1,则a的560次幂与模561对于1同余

Answer 1

首先证明欧拉定理：
欧拉定理内容：在数论中,欧拉定理（也称费马-欧拉定理）是一个关于同余的性质.欧拉定理表明,若n,a为正整数,且n,a互质,(a,n) = 1,则a^φ(n) ≡ 1 (mod 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互质和消去律可以得出.
　　所以,很明显,S=Zn
　　既然这样,那么
　　（a*x1 × a*x2×...×a*xφ(n)）(mod n) 　　
= （a*x1(mod n) × a*x2(mod n) × ... × a*xφ(n)(mod n)）(mod n)
　　= （x1 × x2 × ... × xφ(n)）(mod n)
　　考虑上面等式左边和右边
　　左边等于([a^φ(n)] *（x1 × x2 × ... × xφ(n)）) (mod n)
　　右边等于x1 × x2 × ... × xφ(n)）(mod n)
　　而x1 × x2 × ... × xφ(n)(mod n)和n互质
　　根据消去律,可以从等式两边约去,就得到：
　　a^φ(n) ≡ 1 (mod n)
根据欧拉定理
回头看题目
若（a,561）=1,则a的560次幂与模561对于1同余
无非令n=561 a,n互质 (a,n) = 1 φ(n)=n-1
显然a^φ(n) ≡ a^n-1 ≡a^560≡1(mod 561)