費馬小定理

應用

(A/B)%C 無法計算，要換成乘法： (A*B')%C ，其中 B' 是未知的

假設 power(x,y) 回傳 \(x^y\)

則 B'=power(B,C-2)%C

則 (A/B)%C
=(A*(power(B,C-2)%C))%C
=(A%C)*(power(B,C-2)%C)

重點

費馬小定理提到如果有一個「整數」\(a\) 和一個「質數」\(p\) 那麼

\[
a^p \equiv a \pmod{p}
\]

\[
= a^{p-2} * a^2 \equiv a^{-1} * a^2  \pmod{p}
\]

\[
= a^{p-2} \equiv a^{-1}  \pmod{p}
\]

費馬小定理：「若 \(P\) 為質數，對任意正整數 \(a\) ， \((a^{P-2} \% P)\) 是 \(a\) 在 \([1, P-1]\) 區間的唯一乘法反元素。」

單位元素

在數學中，單位元素是一個在某種運算下保持其他元素不變的元素。這意味著如果你有一個集合和一個二元運算（比如加法或乘法），單位元素在這個運算下與任何集合內的元素結合都不會改變那個元素。舉例來說：

在加、減法中，\(0\) 是加法的單位元素，因為任何數字加 \(0\) 都保持不變（如 \(a + 0 = a\)）。
在乘、除法中，\(1\) 是乘法的單位元素，因為任何數字乘以 \(1\) 都保持不變（如 \(a \times 1 = a\)）。

此外，這個概念也可以擴展到其他數學結構中，例如在矩陣運算中，單位矩陣（對角線上都是 \(1\)，其他地方都是 \(0\) 的矩陣）是乘法的單位元素。

反元素

任意數與反元素進行運算後會得到單位元素

關係：「任意數」(符號)「反元素」=「單位元素」

加減法的反元素為「相反數」，如 \(a+(-a)=0\) 。
乘除法的反元素為「倒數」，如 \(a\times\frac{1}{a}=1\) 、 \(a\div \frac{1}{a}=1\) 。
模運算反元素於下講解

模反元素

在數學中，「模反元素」是指在模算術（Modular arithmetic）中一個數的逆元。給定一個正整數 \(P\) 和一個與 \(P\) 互質的整數 \(a\)，\(a\) 的模 \(P\) 逆元是指一個整數 \(b\)，使得 \(a \times b \equiv 1 \pmod{P}\)，此時 \(b\) 也可記作 \(a^{-1}\)。換句話說，當 \(a\) 和 \(b\) 相乘後除以 \(P\) 的餘數為 1，也就是\((a\times b) \% P=1\)。

為何是乘法不是加減法呢?
因為在做模運算的時候加法減法乘法都能正常運作
\((8+7)\%5=(8\%5+7\%5)\%5\)
\((8-7)\%5=(8\%5-7\%5)\%5\)
\((8*7)\%5=((8\%5)*(7\%5))\%5\)
換成除法時，就無法正常成立，「模反元素」就是為此存在的

問題：我們要計算\((56/7)\%5\)時該怎麼做?

一、我們知道要計算 \(a/b=c\) 時如果想換成乘法，就是讓 \(a\) 乘上 \(b\) 的乘法反元素 \(k\) (\(b\times k=1\))，也就是 \(\frac{1}{b}\) ：
\(a/b=a\times k =a\times\frac{1}{b}=c\)，\(b\times k=1\)

二、那麼我們知道要計算 \((a/b)\%P=c\) 時如果想換成乘法，就是讓 \(a\) 乘上 \(b\) 模 \(P\) 的模反元素 \(k\) (\((b\times k)\%P=1\))：
\((a/b)\%P=(a\times k)\%P =c\)，\((b\times k)\%P=1\)

三、回到問題，所以要求\((56/7)\%5\)時，我們想要換成\((56\times k)\%5\)的話(因為乘法才可以展開)，就要先求\((7\times k)\%5=1\)，經過運算(先直接推的話)，可以得到\(k=3\) ，因為\((7\times 3)\%5=(21)\%5=1\)，所以 \((56/7)\%5\) 可以換成 \((56\times 3)\%5\)：

\((56/7)\%5\)
\(=(56\times 3)\%5\)
\(=(56\%5\times 3\%5)\%5\)
\(=(1\times 3)\%5\)
\(=3\)

到底這個 3 是如何得到的，我們先留個懸念。

求模反元素

我們先試試暴力找法

#include <bits/stdc++.h>
using namespace std;
#define nn "\n"
int _find(int a,int c){
    int b=1;
    for(int i=0;i<c;i++){
        if((a*i)%5==1){
            return i;
        }
    }
    return -1;
}

int main(){
    int b;
    //計算(56/7)%5;
    //(7*k)%5=1
    b=_find(7,5);
    cout<<"計算(56/7)%5"<<nn;
    cout<<"反元素： "<<b<<nn;
    cout<<"答案： "<<(56/b)%5;
}

計算 (56/7)%5 為 (a*b)%c
反元素b=3
答案=3

複雜度為O(P)也就是O(n)，太慢了。
要如何更快找到答案呢？
這時候要用到費馬小定理。

費馬小定理

費馬小定理提到(詳細證明此篇不提)
如果有一個「整數」\(a\) 和一個「質數」\(p\) 那麼 \(a^p \equiv a \pmod{p}\)
有些地方也會寫成 \(a^p-a \equiv 0 \pmod{p}\)
也就是 \(a^p-a\) 為 p 的倍數

將指數拆開得到

\(a^{p-2} * a^2 \equiv a^{-1} * a^2 \pmod{p}\)

接著根據同餘性質得到

\(a^{p-2} \equiv a^{-1} \pmod{p}\)

由上式子可知在\(\pmod{p}\) 時，求 \(a^{p-2}\) 就可以得到 \(a^{-1}\) 也就是得到模逆元

完整推導如下：

根據冪次性質得到：
\(a^p \equiv a \pmod{p}\)
左右拆出 \(a^2\)：
\(a^{p-2} * a^2 \equiv a^{-1} * a^2 \pmod{p}\)
左右消掉(根據同餘性質)
\(a^{p-2} \equiv a^{-1} \pmod{p}\)

便可得到最後結論：

費馬小定理：「若 \(P\) 為質數，對任意正整數 \(a\) ， \((a^{P-2} \% P)\) 是 \(a\) 在 \([1, P-1]\) 區間的唯一乘法反元素。」

再回到前面例子：\((56/7)\%5\)
要求 \(7\%5\) 的模逆元
就是求 \(7^{5-2}\%5=343\%5=3\)

完整運算式：
\((56/7)\%5\)
\(=(56 \times (7^{5-2}\%5))\%5\)
\(=(56 \times (343\%5))\%5\)
\(=(56 \times 3)\%5\)
\(=(56\%5\times 3\%5)\%5\)
\(=(1\times 3)\%5\)
\(=3\)

接下來要思考如何求 \(a^{p-2}\) ，如果慢慢乘上去，複雜度為O(P)，太慢了，情況並沒有改善。

所以要我們可以使用快速幂，就能夠用O(log(P))
就計算出模逆元

#include <bits/stdc++.h>
using namespace std;
#define nn "\n"

int A,P;

int mod(int a,int p){
    if(p==0){
        return 1;
    }
    else if(p%2==0){//2
        return (mod(a,p/2))%P*(mod(a,p/2))%P;
    }
    else{//1
        return (mod(a,p-1))%P*(a)%P;
    }
}

int main(){
    istringstream cin("7 5");
    cin>>A>>P;
    cout<<mod(A,P-2);//to a^(p-2)
}