初等数论中的同余,欧拉定理与费马小定理证明：对于任意整数a,（a,561）=1,都有a560≡1（mod561）,但561是合数.
2019-06-26
初等数论中的同余,欧拉定理与费马小定理
证明：对于任意整数a,（a,561）=1,都有a560≡1（mod561）,但561是合数.
优质解答
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)
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)