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

题目

初等数论中的同余,欧拉定理与费马小定理
证明：对于任意整数a,（a,561）=1,都有a560≡1（mod561）,但561是合数.

答案

561=3*11*173,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)^...