跳到主要内容

最大公因数

欧几里得算法​

又称辗转相除法

求a,ba,b的最大公因数的一个方法

原理​

a/b=q……r=>a=qb+r(a,b)=(b,r)(0,b)=b\begin{gather*} a/b=q……r=>a=qb+r\\ (a,b)=(b,r)\\ (0,b)=b \end{gather*}

过程​

a÷b=q……ra\div b=q……r，即a=q×b+ra=q\times b+r
其中q(quotient)q(quotient)为商，r(remainder)r(remainder)为余数
再将除数和余数做新一轮求余运算
直到求得的余数为0
(a,b)=最终的除数(a,b)=最终的除数

例：

(被除数，除数)=(172,46)=(46,34)=(34,12)=(12,10)=(10,2)(此时余数为0，(a,b)=2)\begin{align*} &(被除数，除数)\\ =&(172,46)\\ =&(46,34)\\ =&(34,12)\\ =&(12,10)\\ =&(10,2)\qquad(此时余数为0，(a,b)=2)\\ \end{align*}

C++代码​

#include<bits/stdc++.h>
using namespace std;
void main()
{
    int a = 0, b = 0, r = 1;
    cin >> a >> b;
    if (b > a)
    {
        b = b - a;
        a = a + b;
        b = a - b;
    }
    while (a % b != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    cout << b;
}

简明证明​

有a,b,r三个数有a,b,r三个数
分别是式子中的被除数，除数和余数：分别是式子中的被除数，除数和余数：

(b,a)=x(b,r)=y(b,a)=x\\ (b,r)=y

由原式可得：由原式可得：

a=qb+r=>a′x=qb′x+r((b,a)=x)=>r=(a′−qb′)x\begin{align*} &a=qb+r\\ =>&a'x=qb'x+r \qquad\small((b,a)=x)\\ =>&r=(a'-qb')x \end{align*}

可得x∣r，同理：可得x\mid r，同理：

a=qb+r=>a=qb′y+r′y((b,r)=y)=>a=(qb′+r′)y\begin{align*} &a=qb+r\\ =>&a=qb'y+r'y \qquad\small((b,r)=y)\\ =>&a=(qb'+r')y \end{align*}

可得y∣a，即可得y\mid a，即

(b,a)∣r(b,r)∣a(b,a)|r\\ (b,r)|a\\

设A,B,R分别为a,b,c的质因数集合设A,B,R分别为a,b,c的质因数集合
则有：则有：

B∩A⊆RB∩R⊆A∴B∩A=B∩RB\cap A\subseteq R\\ B\cap R\subseteq A\\ \therefore B\cap A=B\cap R\\

得证.得证.

裴蜀等式​

又名贝祖定理，裴蜀恒等式等

定理内容​

(a,b)=sa+tb(a,b)=sa+tb

求系数​

Why？
（这里有个误区，裴蜀等式是一个定理，也就是说没有所谓的原理，只有证明过程）
就是欧几里得算法的一个应用
真别按着教科书倒着来
咱正着看

设a=172，b=46设a=172，b=46

a=3×b+34b=1×34+1234=2×12+1012=1×10+210=5×2+0\begin{align*} a=&3\times b +34\\ b=&1\times 34 +12\\ 34=&2\times 12+10\\ 12=&1\times 10+2\\ 10=&5\times 2+0\\ \end{align*}

则则

34=a−3b=>12=b−(a−3b)=4b−a=>10=(a−3b)−2(4b−a)=3a−11b=>2=(4b−a)−(3a−11b)=15b−4a\begin{align*} &34=a-3b\\ =>&12=b-(a-3b)=4b-a\\ =>&10=(a-3b)-2(4b-a)=3a-11b\\ =>&2=(4b-a)-(3a-11b)=15b-4a \end{align*}

∴2=−4×172+15×46\therefore 2=-4\times 172 + 15\times 46

还是代数好用