本文主要是介绍数论 —— 逆元与同余式定理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【同余模公式】
- (A+B)%M = (A%M+B%M) % M
- (A*B)%M = (A%M*B%M) % M
- (A/B)%M = (A*C)%M = (A%M*C%M) % M,其中 B*C≡1(mod M),B、M 互质,C 称为 B 的逆元
(A/B)%M 的推导:(A/B)%M = (A/B) * 1 % M = (A/B)*B*C % M = (A*C) % M
【威尔逊定理】
若 p 为素数,则:
其逆定理同样成立,即:若 ,则 p 为素数
【二次探测定理】
内容:若 p 是素数且 0<x<p,则 仅有的两个解为:x=1,p-1
证明:
由于 ,因此:,也即
因为 p 是素数,因此 p 必然是或整除 x-1 或整除 x+1,由此可推出定理。
【费马小定理】
若 a 为正整数,p 是一质数,则: ,那么
推论:
【欧拉定理】
若 a 与 m 互质,则:
这篇关于数论 —— 逆元与同余式定理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!