费马小定理

概念

1. 定理
   $p$ 为质数， $a$ 为整数且 $(a,p)=1$， 有 $a^{p-1}\equiv1\pmod p$.

2. 证明
   构造质数 p 的完全剩余系$P=\{1,2,3,\cdots p-1\}.$
   同时构造另一完全剩余系$A=\{a,2a,2a,\cdots (p-1)a\}.$
   由完全剩余系的性质，可得$1\times2\times3\times\cdots\times(p-1)≡a\cdot2a\cdot3a\cdot\cdots\cdot(p-1)a\pmod p.$
   即$(p-1)!≡(p-1)!\cdot a^{p-1}\pmod p.$
   $p$为质数，可知 $p\mid(p-1)!+1$，
   故 $((p-1)!,p)=0.$
   同余式两边可同时约去 $(p-1)!$ ，得
   $a^{p-1}≡1\pmod p.$
   Justified.

应用

求乘法逆元： 设 $b$ 为 $a$ 在模 $p$ 意义下的乘法逆元，可表示为 $ab≡a^{p-1}.$
当 $(a,p)=1$ 时，同余式两边可同时乘上 $\frac{1}{a}$ ，故 $b≡a^{p-2}.$
若 $(a,p)\not=1$ 时，则该同余式无解。

code:

//费马小定理求乘法逆元 
#include<bits/stdc++.h>
using namespace std;

long long n , p;
long long quick_power(long long x , long long y) { 
    long long res=1 , temp=x;

    for (long long i=y; i; temp=temp*temp%p , i>>=1) {
        if (i%2==1) {
            res=res*temp%p;
        }
    }

    return res;
}

const int maxn=1e6+5;
long long inv[maxn];
int main() {
    scanf("%lld %lld" , &n , &p);

    for (int i=1; i<=n; i++) {
        inv[i]=quick_power(i , p-2);
        //printf("%lld\n" , inv[i]);
    }

    return 0;
}