三个重要的同余式

您所在的位置：网站首页 › 威尔逊定理的完整证明 › 三个重要的同余式

三个重要的同余式

2024-03-26 22:47| 来源: 网络整理| 查看: 265

首先要明白，以a≡b(modn)为例子

“≡”是数论中表示同余的符号（注意！！这个不是恒等号）

同余的定义是这样的:

给定一个正整数n，如果两个整数a和b满足a-b能被n整除，即(a-b)modn=0，那么就称整数a与b对模n同余，记作a≡b(modn)，同时可成立amodn=b。

也就是相当于a被n整除余数等于b的意思。

威尔逊定理 (p−1)!≡p−1≡−1 (mod p) (p是素数) ((p−1)!)%p=p−1

例题：

HDU 2973 YAPTCHA (威尔逊定理及其逆定理)

解题报告见http://blog.csdn.net/synapse7/article/details/18728157

费马小定理假如p是质数，且gcd(a,p)=1，那么 a^(p-1) ≡1（mod p）即 ( a^(p-1) )%p = 1 我们可以利用费马小定理来简化幂模运算：由于a^(p-1)≡a^0≡1(mod p)，所以a^x(mod p)有循环节，长度为p-1，所以a^x≡a^(x%(p-1))(mod p)

例如，计算除以13的余数，先计算100%（13-1）=4，然后计算(2^(4))%13=3;