【Fermat】费马小定理

【Fermat】费马小定理

引用

CSDN

1.

https://blog.csdn.net/jimmyLuo5/article/details/143805768

费马小定理是数论中的一个重要定理，在算法竞赛和密码学中有着广泛的应用。本文将详细介绍费马小定理的陈述、证明过程，以及其在求解逆元问题中的应用，并给出相应的代码实现。

定理

若存在整数 a ， p 且gcd(a，p)=1，即二者互为质数，则有
a^(p-1) ≡ 1 (mod p)

引理

引理一

若a，b，c为任意3个整数，m为正整数，且gcd(m，c)=1，则当a * c ≡ b * c (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) (mod p)
易知 ((p-1)!，p)=1，同余式两边可约去(p-1)!，得到
a^(p-1) ≡ 1 (mod p)

逆元

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 (mod p).

对比逆元的方程式，可以很容易得到，a关于p的逆元就是 a^(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; 
}

本文原文来自CSDN