数论初步 —— 整除与 gcd

Posted by WildCow on February 25, 2019

写在前面


笑恨平生不存欢愉





1、符号定义


如果 $m > 0$ 且比值 $n / m$ 是一个整数
我们就说 $m$ 整除 $n$
或者 $n$ 被 $m$ 整除
为了让整除充满仪式感,让我们赋予他一个新的符号,记为:


其实大多数地方用的是 $m | n$
不过 $|$ 在过多地方被涉及(绝对值,集合的定义符,条件概率……)
所以这里换过一个
如果 $m$ 不整除 $n$
就记为 $m \nmid n$ (因为找不到 Latex反斜线的否定只好丢人的用了$|$)
然后有两点需要被注意
没有任何数能被 -1 整除
同时这里的讨论是在整数的情况下




2、最大公因子


在上述定义下
那么我们有两个整数 $m$ 和 $n$ 的最大公因子(great common divisor)是能整除他们两者的最大整数

皮一下:

我们可以用他来化简一个分数
对于一个分数 $m / n$ 化简为最简有:
$(m / gcd(n, m)) / (n / gcd(n, m))$
所以我们说一个分数 $m / n$ 是最简分数当且仅当 $gcd(n, m) = 1$
同时特殊的,我们有:
$gcd(0, n) = n$
$gcd(0, 0)$ 没有意义
另一个熟悉的符号是最小公倍数(least common multiple)

如果 $m \leq 0$ 或者 $n \leq 0$
则 $lcm$ 就没意义
$lcm$ 可以用来对两个分数进行通分
不过我们还是把重点放在 $gcd$ 上




3、欧几里得算法


对于两个数 $n$,$m$ 的 $gcd$
常用方法是用欧几里得算法
对给定的 $0\leq m < n$
我们有递归式

例如
我们有 $gcd(12, 18) = gcd(6, 12) = gcd(0, 6) = 6$
简单证明一下就是
设 $t$ 为 $n$,$m$ 的公因子
那么我们令
$n= at$
$m = bt$
那么我们有:
$n \% m = at - \left \lfloor \frac {at}{bt} \right \rfloor bt$
显然依然能被 $t$ 整除




4、扩展欧几里得算法


还有一个基于欧几里得的扩展算法叫做扩展欧几里得
可以用他来计算满足

的整数 $m’$ 和 $n’$
我们有:

  • 如果 $m = 0$
    那么我们直接取 $m’ = 0$,$n’ = 1$
  • 否则

    我们令 $r = n \%m $,然后用 $(r, m)$ 替换 $(m, n)$ 进行下一轮递归,来计算

    由于 $r = n - \left \lfloor \frac{n}{m} \right \rfloor m$
    之前我们也知道 $gcd(r, m) = gcd(m, n)$
    所以我们有
    然后括号拆开移项一下有:

    然后回溯的时候逐项再计算就好了

其实扩展欧几里得首先是在证明欧几里得算法的正确性
假如通过欧几里得算法我们得到了 $gcd(n, m) = d$
那么我们能确定 $m’ $ 和 $n’$ 确定 $m’m + n’n = d$
我们会发现 $m$ 和 $n$ 的公因子必定能整除 $m’m + n’n$
那么他就必定能整除 $d$
即所有公因子 $d’ \leq d$
证毕




5、一个推论


从扩展欧几里得中能有一个很简单的推论

证明很简单,只需要感性认知
那么用处也很简单
假如有一天我们需要对 $n$ 的所有因子求和
那么我们有

可以注意下斜线的方向= =!
这个等式也很好理解
首先因子是成对存在的
即当你 $m$ 遍历 $n$ 的所有因子的时候
你 $n / m$ 也在遍历所有的因子
更一般的
我们有:

可以把把 $k$ 当成在从 1 开始枚举因子
那么对于因子求和的二重式我们有

一个 $n = 6$ 的例子就可以很清楚的看懂了:

另一方面
交换求和方式后我们有:

有一个证明和式很好的方法叫做艾弗森约定
即 $\sum_{k}a_k[p(k)]$
其中 $p(k)$ 为对 $k$ 的正确与否的判断
对于上述求和式
左边有:

右边有:

除了变量名不一样以外其余的都相同



6、来做题吧


HDU - 5528
题解 - http://seventeenjcinta.com/blog/2018/09/09/hdu-5528/
CF - 787A
题解 - 没有