【Fermat】费马小定理

 

定理

---

若存在整数 a ， p 且g c d ( a ， p ) = 1 gcd(a，p)=1gcd(a，p)=1，即二者互为质数，则有
a ( p − 1 ) ≡ 1 ( m o d p ) a^{(p-1)}≡ 1(mod p)
a 
(p−1)
 ≡1(modp)

目录

定理

引理

引理一

引理二

证明

应用

代码

---

 

引理

引理一

---

若a，b，c为任意3个整数，m为正整数，且g c d ( m ， c ) = 1 gcd(m，c)=1gcd(m，c)=1，则当a ∗ c ≡ b ∗ c ( m o d   m ) a*c\equiv b*c(mod\ m)a∗c≡b∗c(mod m)时，有a ≡ b ( m o d   m ) a\equiv b(mod\ m)a≡b(mod m)。

引理二

---

设m是一个整数且m>1，b是一个整数且(m，b)=1。如果a[1]，a[2]，a[3]，a[4]，…a[m]是模m的一个完全剩余系，则b·a[1]，b·a[2]，b·a[3]，b·a[4]，…b·a[m]也构成模m的一个完全剩余系。

证明

若存在2个整数b·a[i]和b·a[j]同余即b·a[i]≡b·a[j](mod m)…(i>=1 && j>=1)，根据引理1则有a[i]≡a[j](mod m)。根据完全剩余系的定义可知这是不可能的，因此不存在2个整数b·a[i]和b·a[j]同余。
所以b·a[1]，b·a[2]，b·a[3]，b·a[4]，…b·a[m]构成模m的一个完全剩余系。
构造素数 的完全剩余系
p={1，2，3，…，p-1}.
因为 ，由引理2可得
A={a，2a，3a，…，(p-1)a}.
也是p的一个完全剩余系。由完全剩余系的性质，
123*…(p-1)≡a2a3a…*(p-1)a(mod p).
即
( p − 1 ) ! ≡ ( p − 1 ) ! ∗ a ( p − 1 ) ( m o d   p ) (p-1)!≡(p-1)!*a^{(p-1)}(mod\ p)(p−1)!≡(p−1)!∗a 
(p−1)
 (mod p)
易知 ((p-1)!，p)=1，同余式两边可约去(p-1)!，得到
a ( p − 1 ) ≡ 1 ( m o d p ) a^{(p-1)}≡1(mod p)a 
(p−1)
 ≡1(modp)

逆元：ax≡1（mod p）当a和p互质时，方程的解 x 称为a关于p的逆元，

在普通的四则运算中，只有加减乘三种运算可以进行分别取余运算，因为这三种运算都是从低位到高位的运算，而对于除法是从高位到低位的运算，显然不能直接进行取余，这时候，就要用到逆元有关的运算。

逆元可以近似的看作倒数的概念

应用

---

例如，

如果要求（x / y）%p ，显然不可以（x%p）/（y%p），

利用逆元运算：可以将（x / y）%p化为 （x * Y ）%p ，其中Y是y关于p的逆元

那么怎么求Y呢：

由逆元的定义，有y • Y≡1（mod p），

费马小定理：如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡ 1（mod p）。

我们分离一项出来 a • a ( p − 2 ) ≡ 1 ( m o d   p ) a • a^{(p-2)} ≡ 1(mod\ p)a•a 
(p−2)
 ≡1(mod p).

对比逆元的方程式，可以很容易得到，a关于p的逆元就是 a ( p − 2 ) a^{(p-2)}a 
(p−2)
 ，那么Y = y ( p − 2 ) 。 Y=y^{(p-2)}。Y=y 
(p−2)
 。

代码

根据上述推断，根据快速幂可推得：

---

/* 除法取模模板 */
ll quick(ll a,ll b,ll c)//快速幂取模 
{ll ans=1;a%=c;while(b){if(b&1) ans=ans*a%c;a=a*a%c;b>>=1;}	return ans%c;
}ll divi(ll a,ll b,ll p)
{b=quick(b,p-2,p);	//b的逆元return a*b%p; 
}