《數論概論》讀書筆記 第6章 線性方程與最大公約數

這章講的就是歐幾裡得算法和 exgcd 。

原式: ax+by=gcd(a,b) (假設 a≥b )

當 b=0 時有 gcd(a,b)=a ,此時 x=1,y=0

當 b 不為 0 時,根據歐幾裡得定理 gcd(a,b)=gcd(b,a%b) 可得 ax+by=gcd(a,b)=gcd(b,a%b)=bx'+(a%b)y', .

即 :

ax+by=bx'+(a%b)y'=bx'+(a−b∗⌊ab⌋)y'

移項得

ax+by=bx'+(a%b)y'=ay'+b(x'−⌊ab⌋y')

根據恒等定理,有

x=y'

y=x'−⌊ab⌋y'

習題解析：

6.1

(a)12345x+67890y=gcd(12345,67890) 的一組整數解為 x=11，y=−2

(b)54321x+9876y=gcd(54321,9876) 的一組整數解為 −1645,y=9048

6.2

(a)x=−53+121k,y=46−105k

(b)x=11+4525k,y=−2−823k

(c)x=−1645+3292k,y=9048−18107k

6.3

根據上面的推導，可以得到：

#include <iostream>
#include<algorithm>
#include <cstdio>
typedef long long ll; 
using namespace std;
int x,y,q;
void ex_Eulid(int a,int b){
    if(b==){
        x=;y=;q=a;
    }
    else{
        ex_Eulid(b,a%b);
        double temp=x;
        x=y;y=temp-a/b*y;
    }
}
ll exgcd(ll a,ll b,ll &x,ll &y)// 傳回a,b的最大公約數  
{  
    if(!a && !b)return -;  
    if(!b)return x=,y=,a;  
    ll d=exgcd(b,a%b,y,x);  
    return y-=a/b*x,d;  
}  
int main() {
    int a,b;
    cin>>a>>b;
    if(a<b)swap(a,b);
    ex_Eulid(a,b);
    printf("%d=(%d)*%d+(%d)*%d\n",q,x,a,y,b);
    return ;
}
           

6.4

本問題将二進制一次方程拓展到三元的情況，即求 ax+by+cz=1 的整數解。思路就是把一個三元一次方程變成解兩個二進制一次不定方程，對于該三元一次方程有無整數解的問題，即如果 gcd(a,b,c)=1 則有解，否則無解。

6.5

思路就是把 ax+by=gcd(a,b) 拓展到 ax+by=k∗gcd(a,b) 的情況，隻需要把特解拿出來乘以 k ，再轉化成通解即可。

相同的例題：

CF #7 C. Line （擴充歐幾裡得）

運用：

（1）求解模的逆元

同餘ax≡b(modn)，如果 gcd(a,n)==1 ，則方程隻有唯一解。

在這種情況下，如果 b==1 ，同餘方程就是 ax=1(modn),gcd(a,n)=1 。

這時稱求出的 x 為 a 的對模 n 乘法的逆元。

對于同餘方程 ax=1(modn) ， gcd(a,n)=1 的求解就是求解方程

ax+ny=1，x,y 為整數。這個可用擴充歐幾裡德算法求出，原同餘方程的唯一解就是用擴充歐幾裡德算法得出的 x 。

比如，乘法逆元則是在計算 (a/b)%mod 時，可以轉化為( a∗b 的逆元) %mod ，如果 b 過大，可能需要取餘，而 a/(b%mod)%mod 顯然是錯誤的，這裡就可以利用乘法逆元求出結果。

（2）求解模線性方程（線性同餘方程）

同餘方程 ax≡b(modn) (也就是 ax%n=b ) 對于未知數 x 有解，當且僅當 gcd(a,n)|b (也就是 b%(gcd(a,n))==0 )。且方程有解時，方程有 gcd(a,n) 個解。

求解方程 ax≡b(modn) 相當于求解方程 ax+ny=b,(x,y 為整數)。

（3）轉化

然而我們要将一些普通的式子轉化成類似同餘的形式。

比如：

ak=bt+A

那麼我們可以變成同餘于 b 的式子：

ak≡A(modb)