初等数论与算法（一）：整除、最大公约数、最小公倍数、辗转相除法、裴蜀定理

■\(=<+>\)

■\(=<>\)

最大公因数

公因数定义：假设有一组正整数\(a_1,a_2,...,a_n\)，若\(d~|~a_1,d~|~a_2,...,d~|~a_n\)则称\(d\)为\(a_1,a_2,...,,a_n\)的公因数

最大公因数定义：假设有一组正整数\(a_1,a_2,...,a_n\)，若\(d_1,d_2,...,d_n\)是这一组数的公因数，则\((a_1,a_2,...,a_n)=max{d_1,d_2,...,d_n}\)称为最大公因数，简记为\(m\)

■\(m~|~a_i\)

■\(1≤m≤min(a_i)\)

■\(d_i~|~m\)（最大公约数是其他公约数的约数）

■\((a,b)≥n\)，当且仅当\(\begin{cases}n~|~a \\ n~|~b \end{cases}\)（证明要用到的重要结论！！！）

这个性质不难理解，由公因数的定义可得，因为n是公因数，那么肯定是要小于等于最大公因数的。但这里存在一个转换思路的过程。也就是如果要证明有关不等式的问题，可以将这个问题转成整除问题

■若\(m~|~a,m~|~b\)，则\(m~|~(a,b)\)

■\((a,b)~|~a，(a,b)~|~b\)

■若\(a=bq+r\)即满足余数定义且\(a,b∈N_+\)，则\((a,b)~=~(b,r)=r_n\)（欧几里得算法）

证明：

? 要证明\((a,b)~=~(b,r)\)即证明\(\begin{cases} (a,b)≤(b,r) \\ (b,r)≤(a,b) \end{cases}\)

? 这里只说明其中一条其余可自证

? 由整除性第二条性质得要证明\((a,b)≤(b,r)\)即证明\(\begin{cases}(a,b)≤b \\ (a,b)≤r \end{cases}\)

? \(∵(a,b)~|~b\)

? \(∴(a,b)≤b\)

? \(∵r=a-bq\)

? \(∴(a,b)~|~(a-bq)\)（整除性第四条性质，已略部分步骤）

? \(∴(a,b)≤(b,r)\)

? 同理可得\((b,r)≤(a,b)\)

? \(∴(a,b)=(b,r)\)

比如要求解\((a,b)\)可以‘先求解\((b,r)\)直到最后\(r\)变小至0即可，在后面详细描述了欧几里得算法的实现即到最后会得到一个\((x,0)\)的一组数，那么\(x=(a,b)\)

■若\(a,b∈N_+\)，则\((a,b)=ma+nb\)

证明：

? 本质上是欧几里得算法的逆过程

? \(a = bq_1+r_1\)

? \(b = r_1q_2 + r_2\)

? \(...\)

? 可以用一个四元组表示这四个数

? \(→→...→\)

? \(r_{n+1} = 0\)

? 其中定义\(a,b,r_i\)前的系数统一定为\(C\)

（注意引入的\(C\)是一个表示任意的常数，C和C不一定相等）

? \(r_{n-1}=Cr_n\)

? \(r_{n-2}=Cr_n+r_n\)

? \(r_{n-3}=Cr_n+r_{n-1}\)

? \(r_{n-4}=Cr_{n}+Cr_{n-1}+r_{n-2}=Cr_n\)

? 简单来说就是不管是第几项都可以通过不断回代得到\(Cr_n\)至于\(C\)为多少需要计算

? 那么在第一项就可以这么表达

? \(a=Cb+r_1=Cb+Cr_n\)→\(r_n=Ca+Cb=ma+nb\)

? 由此得证

? 具体算法求解m、n贴在了后面

■绝对最小剩余：若满足余数定义\(a=bq+r\)且\(|r|≤\frac{b}{2}\)，此时\(|r|\)称为绝对最小剩余

在欧几里得算法上运用绝对最小剩余在某些情况下可以优化次数

但首先要将一个非负最小剩余处理为绝对最小剩余

\(\begin{cases}r,r ≤ b/2,a=qb+r \\ r-b,b/2

简单来说就是如果发现不满足绝对最小剩余，可以q+1后r再减去b从而得到一个满足绝对最小剩余的余数（这里不作证明）

具体算法参考后面，只是多了一个判断就能优化

欧几里得算法（辗转相除法）

问题描述：已知性质\((a,b)=(b,r)\)，如何求解正整数\(a\)、\(b\)的最大公因数？

数学解决

\((a,b)=(b,r_1)=(r_1,r_2)=...=(r_{n-1},r_{n})=(r_n,0)=r_n\)

\(a=bq_1+r_1\)

\(b=r_1q_2+r_2\)

...

\(r_{n-1}=r_nq_{n+1}+r_{n+1}\)

\(∵r_{n+1}=0\)

\(∴r_{n}=(r_n,0)=(r_{n-1},r_n)=...=(a,b)\)

程序解决

//假设a>b,即a为被除数,b为除数
int gcd(int a,int b){
    return (b) ? gcd(b,a%b) : a ;
}

绝对最小剩余优化欧几里得算法

绝对最小剩余在某些情况下可以优化近一半的次数

比如gcd(288,158)

简单来说就是发现不满足绝对最小剩余的条件

■q变为q+1

■r变为r-b

（但是传参时为正数所以具体实现上r要变成b-r）

int gcd(int a, int b) {
    int r = a % b;
    if (r > b / 2)r = (b-r);
    return (r) ? gcd(b, r) : b;
}

推广：求解多个数的最大公约数

上面已经知晓了欧几里得算法求解两个数的最大公约数，如果要求解多个，其实也相当简单

（1）定理说明

假设有n个数，\(a_1,a_2,...a_n\)

\((a_1,a_2)=d_2\)

\((d_2,a_3)=d_3\)

\(...\)

$(d_{n-1},a_n)=d_n $

\(∴(a_1,a_2,...,a_n)=(d_{n-1},a_n)=d_n\)

数学证明略， 比较简单，可以用数学归纳法证明

同理可以推广得到裴蜀定理

\((a_1,a_2,...,a_n)=∑x_ia_i\)

（3）程序求解

//已知int gcd(int a,int b);
//备注:保证n>=2且传入参数均正整数，不作异常判断
int gcd(vector n) {
    int len = n.size();
    int d = gcd(n[0], n[1]);
    for (int i = 2; i < len; i++) {
        d = gcd(d, n[i]);
    }
    return d;
}

裴蜀定理引入（又称扩展欧几里得算法）

先来个具体案例，假设要求a=288,b=158的公因数，先尝试用欧几里得算法得到具体过程

/*
288=1*158+130
158=1*130+28
130=4*28+18
28=1*18+10
18=1*10+8
10=8*1+2
8=2*4
此时(a,b)=(r(n),0)=2
*/

裴蜀定理相当于回代的过程

简单来说就是除数当作上一情况的余数做回代
如2是最后情况的除数,确实是倒数第二步的余数，同理可得其他情况
因此抽象成递推式得到

当前情况：\(r_{i-1}=r_iq_{i+1}+r_{i+1}\)

上一情况：\(r_{i-2}=r_{i-1}q_{i}+r_i\)

当前情况的除数是\(r_i\)

由上一情况转换得

\(r_{i}=r_{i-2}-q_{i}r_{i-1}\)

根据欧几里得算法我们是知道传入的前两个数的

即已知当前情况的\(r_{i-1},r_{i}\)和上一情况的\(r_{i-2},r_{i-1}\)

所以也就剩下\(q_i\)未知，因此可以求得

\(q_{i}=r_{i-2}/r_{i-1}\)（整除）

因此只要知道最基本的情况，不断求解\(q_i\)即可回到第一步

但现在还少点东西，之后算法的实现还会用到上述证明过程，先看转换的具体的过程

/*
2=10-8*1			(1)2是最初的除数

 =10-(18-10*1)*1		(2)转8
 =2*10-18
 
 =2*(28-18)-18			(3)转10
 =2*28-3*18
 
 =2*28-3*(130-4*28)		(4)转18
 =14*28-3*130
 
 =14*158-17*130			(5)转28
 
 =31*158-17*288			(6)转130

∴(a,b)=31b-17a
*/

反推来看，设系数\(x,y\)满足\(ax+by=(a,b)\)

扩展欧几里得算法即求解最大公约数的同时带出系数

裴蜀定理证明与算法实现

现在考虑一般的递推的具体情况

基本情况：

\((r_n,0)\)时，等式为\((a,b)=x_{n}r_{n}+y_n*0\)

此时\(x=1,y=0\)（理论上y可以为任何值，但为了方便，约定为0）

而回代的过程在于将当前情况的除数回代成为上一情况的余数

根据之前推导的\(r_{i}=r_{i-2}-q_{i}r_{i-1}\)和\(q_{i}=r_{i-2}/r_{i-1}\)（整除）

\((a,b)=x_n(r_{n-2}-r_{n-1}q_n)\)

接下来只要一步一步推导即可，从\(r_n\)一直反推到\(b\)

递推情况：

已知在\((r_{i-1},r_{i})\)有\((a,b)=x_{i-1}r_{i-2}+y_{i-1}r_{i-1}\)

根据推导对\(r_{i-1}\)展开

在\((r_{i-2},r_{i-1})\)有\((a,b)=x_{i-1}r_{i-2}+y_{i-1}(r_{i-3}-?\frac{r_{i-3}}{r_{i-2}}?r_{i-2})=y_{i-1}r_{i-3}+(x_{i-1}-?\frac{r_{i-3}}{r_{i-2}}?)r_{i-2}\)

再简化成系数的变化（重要结论！！！）

\(x_{i-2}=y_{i-1} \\ y_{i-2}=x_{i-1}-?\frac{r_{i-3}}{r_{i-2}}?y_{i-1}\)

得到了这个结论后就可以来实现算法了

int exgcd(int a, int b, int &x, int &y) {
    //递归,当b=0时即裴蜀定理的初始情况
    //大体功能不变,依然返回(a,b)
    if (!b) {
        x = 1;
        y = 0;//y值说过可以随意改
        return a;
    }
    int gcd = exgcd(b, a%b, x, y);
    int t = y;
    y = x - a / b * y;
    x = t;
    //简单来说就是求出(a,b)以及更新系数
    //更新前后的顺序自己需要捋顺
    //这属于程序问题而不是数学问题
    return gcd;
    //细节备注:算法是要先知道初始的x,y才能继续更新
    //因此先定义gcd达到初始情况定义x,y
}

最小公倍数

公倍数与公因数是相互对偶的概念，之间存在联系

公倍数定义：假设有一组正整数\(a_1,a_2,...,a_n\)，若\(a_1~|~m,a_2~|~m,...,a_n~|~m\)则称\(m\)为\(a_1,a_2,...,,a_n\)的公倍数

最小公倍数定义：假设有一组正整数\(a_1,a_2,...,a_n\)，若\(m_1,m_2,...,m_n\)是这一组数的公倍数，则\([a_1,a_2,...,a_n]=min{m_1,m_2,...,m_n}\)称为最小公倍数，简记为\(n\)

定理

■\(a_i~|~n\)

■\(n≥max(a_i)≥1\)

■\(n~|~m_i\)（其他公倍数是最小公倍数的倍数）

■\([a,b]≤n\)，当且仅当\(\begin{cases}a~|~n \\ b~|~n \end{cases}\)（证明要用到的重要结论！！！）

■若\(a~|~m,b~|~m\)，则\([a,b]~|~m\)

■\([a,b](a,b)=ab\)（重要结论！！！）

（2）数学证明

? 首先将形式转变：\((a,b)=\frac{ab}{[a,b]}\)

? 要证明这个即证明两方面\(\begin{cases}(a,b)≤\frac{ab}{[a,b]} \\ (a,b)≥\frac{ab}{[a,b]} \end{cases}\)

? （之前证明过类似的）

? 这里只证明其中一点，要证明\((a,b)≤\frac{ab}{[a,b]}\)即证明\(\begin{cases}\frac{ab}{[a,b]} ~|~a \\ \frac{ab}{[a,b]}~|~ b\end{cases}\)

? 同样只证明一个

? 由于这个式子非常特殊你可以轻易地写出

? \(a=(\frac{ab}{[a,b]})(\frac{[a,b]}{b})\)

? 而且对于这个式子\(\frac{ab}{[a,b]}\)是整数（根据公倍数性质得到）

? \(\frac{[a,b]}{b}\)是整数（根据公倍数性质得到）

? \(∴{[a,b]} ~|~a\)

? 同理可得...

? \(∴\frac{ab}{[a,b]}~|~a\)

? 对于\((a,b)≥\frac{ab}{[a,b]}\)

? 最大公因数的性质无法将不等式转换成一组整除

? 但替换后\([a,b]≥\frac{ab}{(a,b)}\)最小公倍数可以将不等式转换一组整除\(\begin{cases}a~|~\frac{ab}{(a,b)} \\ b~|~\frac{ab}{(a,b)} \end{cases}\)

? 同理可得...

? 因此证得公式

? 可以发现证明等于的问题基本就是等于转不等式，不等式再根据最大公因数或最小公倍数的特点转成整除问题即可。整除问题只要能找到整数和整的除数相乘得到整的被除数即可。因此转换成了最小的问题是不是整数的问题，这个不难证明

（3）程序求解

/*已知之前所写的函数*/
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}

推广：求解多个数的最小公倍数

与之前类似

//备注:保证n>=2且传入参数均正整数，不作异常判断
int lcm(vector n) {
    int len = n.size();
    int m = lcm(n[0], n[1]);
    for (int i = 2; i < len; i++) {
        m = lcm(d, n[i]);
    }
    return m;
}

推广：裴蜀定理

同理最大公约数可以推广，自然其扩展的算法当然也可以，但计算时更加复杂，这里给出我个人的解答，不代表没有其他解法

假设有一堆数\(n[0],n[1],...,n[N]\)

推广的裴蜀定理就是\(∑_ix[i]n[i]=(n[0],n[1],...,n[N])\)

如何求解各个系数呢？

和推广的欧几里得算法一致，先算前两项，然后\(d\)作为参数计算后面的项

\(d=(n[0],n[1])\)

算出第一项并带出\(x[0],x[1]\)

即式子是\(d=x[0]n[0]+x[1]n[1]\)

然后将\(d\)看成一整项，求解\(d'=(d,n[2])\)

最后也会求出系数，d的系数定为combine

即\(d'=combine*d+x[2]n[2]=combine*x[0]n[0]+combine*x[1]n[1]+x[2]n[2]\)

那么combine会作用到之前所求的所有数之上

...

//备注:保证n>=2且传入参数均正整数，不作异常判断
int exgcd(vector n, vector &x) {
    //x[i]存储n[i]的系数
    //需要保证n.size()=x.size()
    int len = n.size();
    
    int d = exgcd(n[0], n[1], x[0], x[1]);
    int combine;
    //combine用于指定联合的系数最后x[j]要乘上的
    for (int i = 2; i < len; i++) {
        d = exgcd(d, n[i], combine, x[i]);
        for (int j = 0; j < i; j++) {
            x[j] *= combine;
        }
    }
    return d;
}

本章结束代码

在每章结束后我会附上完整的代码你是可以直接运行的

而代码会是本章讲到的一个内容的完整版

//推广的裴蜀定理
#include
#include
#include
using namespace std;

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    int gcd = exgcd(b, a%b, x, y);
    int t = y;
    y = x - a / b * y;
    x = t;
    return gcd;
}

//备注:不作异常判断
int exgcd(vector n, vector &x) {
    int len = n.size();
    
    int d = exgcd(n[0], n[1], x[0], x[1]);
    int combine;
    for (int i = 2; i < len; i++) {
        d = exgcd(d, n[i], combine, x[i]);
        for (int j = 0; j < i; j++) {
            x[j] *= combine;
        }
    }
    return d;
}

int main() {
    vector n;
    n.push_back(288);
    n.push_back(158);
    n.push_back(77);
    vector x(3, 0);
    cout << exgcd(n,x) << endl;
    cout << x[0] << "\t" << x[1] << "\t" << x[2] << endl;
    return 0;
}