Question

初等数论中的同余，欧拉定理与费马小定理

证明：对于任意整数a，（a，561）=1，都有a560≡1（mod561），但561是合数。

Answer 1

561=3*11*17
3,11,17都是质数
且，因为 (a,561)=1,所以 (a,3)=1,(a,11)=1,(a,17)=1
根据费马小定理有：
a^2≡1 这样 (a^2)^280≡1，即 a^560≡1 (mod 3)
a^10≡1 这样 (a^2)^56≡1，即 a^560≡1 (mod 11)
a^16≡1 这样 (a^2)^35≡1，即 a^560≡1 (mod 17)
而 3,11,17都是质数，所以
a^560≡1 (mod 3*11*17)
即 a^560≡1 (mod 561)