神马作文网初等数论中的同余,欧拉定理与费马小定理
来源：学生作业帮 编辑：神马作文网作业帮 分类：综合作业 时间：2024/11/13 20:26:17
初等数论中的同余,欧拉定理与费马小定理
证明：对于任意整数a,（a,561）=1,都有a560≡1（mod561）,但561是合数.
证明：对于任意整数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)
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)