费马小定理
2022/2/18 23:42:55
本文主要是介绍费马小定理,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、概念
费马小定理:a^(p-1)≡1(modp) (a,p)=1//a与p互素
a*(p-1)≡1(modp)相当于 a^(p-1)modp==1modp
完全剩余系:将对一个数m取余,余数相同的一类数称呼同余类(比如1mod3=1,4mod3=1。1,4为模m的同余类)。
那么一个数m 便有0~m-1(m个同余类),各取一个便是完全剩余系。
二、引理
引理1:a*c≡b*c(mod p) a≡b(mod p) (c,p)=1
(a*c-b*c) mod p=0
(a-b)*c mod p=0 //因为c,p互质,所以a-b=kp
所以 (a-b)modp=0;
a≡b(mod p)
引理2:取p的完全剩余系 a1,a2,a3....ap,将他们全部乘以m(m与p互质),a1*m,a2*m...ap*m依旧是p的完全剩余系;
要证明定理2可采取反证法,即证明a1*m,a2*m...ap*m 有两个相同即不是p的完全剩余系
ai*m≡aj*m(modp)
ai≡aj(mod p) (定理1)
已知ai,aj不是同余类,矛盾,所以反证了定理2
三、证明
取p的完全剩余系 1,2....p-1,将他们全部乘以a(a与p互质),a,2*a...(p-1)*a依旧是p的完全剩余系;(引理2)
所以可得 1*2....p-1≡ a,2*a...(p-1)*a(mod)
1*2....p-1≡ 1*2....p-1*a^(p-1)(mod)
(p-1)!≡ (p-1)!*a^(p-1)(mod)
1≡ a^(p-1)(mod)
a^(p-1)≡1(modp) (a,p)=1 //证毕
这篇关于费马小定理的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现