浅谈数论

待更

欧几里得算法

gcd(a,b)=gcd(b,a%b)

说人话就是辗转相除法

证明:

$$
令a=bk+c
\
\therefore c=a-bk
\
设有公约数d|a,d|b
\
\therefore \frac{a}{d}-\frac{b}{d}k=\frac{c}{d}
\
\therefore d|c
$$

此处使用递归实现

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

扩展欧几里得算法

使用欧几里得算法处理不定方程$ax+by=gcd(a,b)$
$$
ax+by=gcd(a,b)
=gcd(b,a;mod;b)
=bx'+(a;mod;b)y'
\
=bx'+(a-\lfloor\frac{a}{b}\rfloorb)*y'
=ay'+b(x'-\frac{a}{b}y')
\
\because ax+by=ay'+b(x'-\frac{a}{b}y')
\
\therefore
\begin{cases}
x=y'
\
y=x'-\frac{a}{b}y'
\end{cases}
$$

由此不断递归，当$gcd=0$时得
$$
\begin{cases}
x=1
\
y=0
\end{cases}
$$

其实现如下

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