《数论概论》读书笔记第6章线性方程与最大公约数

- 日理万妓 2022-06-14 05:20 221阅读 0赞

这章讲的就是欧几里得算法和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==0){
            x=1;y=0;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 -1;  
        if(!b)return x=1,y=0,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 0;
    }

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 （扩展欧几里得）][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)

[CF _7 C. Line]: http://blog.csdn.net/liangzhaoyang1/article/details/70036591