数论知识-最大公约数
Xhyukhalt
·
·
个人记录
upd\ in\ 2021.08.14:
-
在 最大公约数的特征 处补充了裴蜀定理的内容
-
修正了a \bmod b一类的格式问题。
-
将结尾的例题放到了对应内容的位置。
整除性与约数
符号d \mid a（读作“d整除a”）的含义是，存在某个整数k，使得a=kd。
任何整数均可整除0。
如果a>0且d \mid a，那么|d|≤|a|。
如果d \mid a，则称a是d的倍数。
如果d不能整除a，则写作d \nmid a。
如果d \mid a且d≥0，则称d是a的约数。
非零整数$a$的约数至少应为$1$，且不会大于$|a|$。
任何正整数$a$都可以被**平凡约数**$1$和其自身$a$整除，整数$a$的**非平凡约数**称为$a$的**因子**。
## 除法定理
对于任何整数$a$和任何正整数$n$，存在唯一整数$q$和$r$，满足$0≤r<n$且$a=qn+r$。
称$q=\lfloor a/n \rfloor$为除法的**商**，值$r=a \bmod n$为出发的**余数**。
$n \mid a$ 当且仅当$a \bmod \ n=0$。
## 公约数与最大公约数
如果$d$是$a$的约数并且$d$也是$b$的约数，那么$d$是$a$与$b$的公约数。
$1$是任意两个整数的**公约数**。
公约数的重要性质：
$d \mid a$且$d \mid b$蕴含着$d \mid (a+b)$且$d \mid (a-b)
更一般地，对任意整数x和y，有:
d \mid a$且$d \mid b$蕴含着$d \mid (ax+by)
如果a \mid b，那么|a|≤|b|，或者b=0，而这说明:
a \mid b$且$b \mid a$蕴含着$a=\pm b
两个不同时为0的整数a与b的公约数中最大的称为其最大公约数，记作\gcd(a,b)。
定义\gcd(0,0)=0，该定义是使gcd函数的基本性质的等式普遍成立所必不可少的。
最大公约数的基本性质
\gcd(a,b)=\gcd(b,a)
\gcd(a,b)=\gcd(-a,b)
\gcd(a,b)=\gcd(|a|,|b|)
\gcd(a,0)=|a|
\gcd(a,ka)=|a|(\forall k \in \mathbb{Z})
最大公约数的特征
如果任意整数a和b不都为0，则\gcd(a,b)使a与b的线性组合集\{ax+by: x,y \in \mathbb{Z}\}中的最小正元素。
upd\ in\ 2021.8.14:
这个特征和裴蜀定理讲的是一件事情。
裴蜀定理，又称贝祖定理，其内容为：
设a,b是不全为0的整数，则存在整数x,y，使得ax+by=\gcd(a,b)。
只不过特征里没有提到，\gcd(a,b)是线性组合集里最小的正元素。
这里有一道裴蜀定理的练习题：
LuoguP4549 【模板】裴蜀定理
推论1
对任意整数a和b，如果d \mid a 且d \mid b，则d \mid \gcd(a,b)。
（由\gcd(a,b)=ax+by显然得证）
推论2
对所有整数a和b以及任意非负整数n，有
\gcd(an,bn)=n \gcd(a,b)
\gcd(an,bn)=anx+bny=n(ax+by)=n\gcd(a,b)
下面这道题目用到了这个推论：
[NOIP2009提高组 Hankson的趣味题](https://www.luogu.com.cn/problem/P1072)
题目解答笔记：
[Hankson的趣味题_笔记](https://www.luogu.com.cn/blog/60994/xhyu61-13-noip2009TGT2)
#### 推论3
对于任意正整数$n,a,b$，如果$n \mid ab$且$\gcd(a,n)=1$，则$n \mid b$。
感性理解很容易，如果$ab$这个数拆成了$a×b$的形式，$n$不能将$a$整除，那就只能将$b$整除了。
一个草率且不一定正确的证明如下：
由$n \mid ab$，设$ab=kn$。
$$\gcd(a,n)=\gcd(\frac{kn}{b},n)=n\gcd(\frac{k}{b},1)=1$$
$$n\gcd(k,b)=b$$
$$\gcd(k,b)=\frac{b}{n}$$
而$\gcd(k,b) \in \mathbb{Z}$，故得$n \mid b$。
## 互质数
如果两个整数$a$与$b$只有公约数$1$，即$\gcd(a,b)=1$，则$a$和$b$称为互质数。
### 定理
对任意整数$a,b,p$，如果$\gcd(a,p)=1$且$\gcd(b,p)=1$，则$\gcd(ab,p)=1$。
证明：
由定理得
$$ax+py=1$$
$$bx'+py'=1$$
等式两边分别相乘，整理得
$$ab(xx')+p(ybx'+y'ax+pyy')=1$$
而$1$是$ab$与$p$的一个正线性组合，所以根据最大公约数的特征，得到$\gcd(ab,p)=1$。
~~暴力证明法~~
## GCD递归定理
对任意非负整数$a$和任意正整数$b$：
$$\gcd(a,b)=\gcd(b,a\bmod \ b)$$
## 欧几里得算法
欧几里得算法是通过$GCD$递归定理计算两个非负整数的最大公约数的算法。
其实就是高中数学里面学习的辗转相除法。
代码如下：
```cpp
int EUCLID(int a, int b)
{
return (!b) ? a : gcd(b, a % b);
}
```
### 欧几里得算法的运行时间
首先介绍斐波那契数列$F_k$：
$$
F_k =
\begin{cases}
0 \qquad & k = 0 \\
1 \qquad & k = 1 \\
F_{k-1}+F_{k-2} & k>1
\end{cases}
$$
#### 引理
如果$a>b≥1$并且$EUCLID(a,b)$执行了$k≥1$次递归调用，则$a≥F_{k+2},b≥F_{k+1}$。
~~（好像平时也不会用这个引理）~~
#### Lamé定理
对任意整数$k≥1$，如果$a>b≥1$，且$b<F_{k+1}$，则$EUCLID(a,b)$的递归调用次数少于$k$次。
已知$\phi=\frac{1+\sqrt{5}}{2}$，即黄金分割率。
$F_k$约为$\frac{\phi^k}{\sqrt{5}}$，所以$EUCLID$执行中递归调用次数为$O(lg \ b)$。
将这个界限改进，可以改进到至多执行
$$1+\log_{\phi}{(b/\gcd(a,b))}$$
次递归调用。
## 扩展欧几里得算法
在欧几里得算法中，我们只能输入两个非负整数，输出这两个数的最大公约数。
但现在我们有了新的需求：想知道满足下列条件的整系数$x$和$y$：
$$d=\gcd(a,b)=ax+by$$
这里的$x$和$y$可能为$0$或负数。
我们对$EXTENDED-EUCLID$输入一对非负整数，其返回一个满足上面式子的一个三元组$(d,x,y)$。
代码如下：
```cpp
int EXTENDED_EUCLID(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1; y = 0;
return a;
}
else
{
int ret = EXTENDED_EUCLID(b, a % b, y, x);
y -= a / b * x;
return ret;
}
}
```
### 过程分析
我们发现，扩展欧几里得中$a$和$b$的作用依旧是在计算最大公约数，和欧几里得算法的区别仅在于$x$和$y$的计算。
首先分析，当$b=0$时，在欧几里得算法当中，我们直接返回$a$。在这里，我们注意到，根据最大公约数的性质，我们有
$$\gcd(a,0)=a=a×x+0×y$$
显然，这里$x=1$，至于$y=0$，一个感性理解就是，我们所求的最大公约数是$ax+by$集合的最小数，而当我们返回的时候，其实是返回一个三元组$(d,x,y)$，那么返回之后，为了使$ax+by$是个最小的元素，那么令$y=0$。
~~纯粹瞎编~~
当递归回上一层之后，我们设返回过来的三元组为$(d',x',y')$，其中
$$
d'=\gcd(b,a \bmod\ b)=bx'+(a\bmod\ b)y'
$$
根据取模的性质，有
$$
a\bmod\ b = a-b\lfloor a/b \rfloor
$$
故
$$
d'=bx'+(a\bmod\ b)y'=bx'+(a-b\lfloor a/b \rfloor)y'
$$
整理得
$$
d'=ay'+b(x'-\lfloor a/b \rfloor y')
$$
因此，只需要选择$x=y'$和$y=x'-\lfloor a/b \rfloor y'$时，就可以满足等式$d=ax+by$。
从而证明了扩展欧几里得算法的算法的正确性。
### 递归调用次数
我们发现，在计算最大公约数的部分，扩展欧几里得算法和欧几里得算法的过程完全一样，所以，欧几里得算法和扩展欧几里得算法的时间也相同，两者相差不会超过一个常数因子，所以扩展欧几里得算法的递归调用次数也是$O(log \ b)$。