数论（一）

1.同余系统

1.1 最大公约数(Greatest common divisor)

1.1.1 $gcd(x,y)$表示x和y的最大公约数，也叫最大公因数，例如$gcd(6,15)=3$

欧几里得对“公约”的解释，给定两条长度不同的线段 a 和 b ，如果能够找到第三条线段 c ，它既可以度量 a ，又可以度量 b ，我们就说 a 和 b 是可公约的(commensurable)，最大可能的c就是a和b的最大公约数

1.1.2 如果两个数的最大公约数是1，那么这两个数成是互质的(relatively prime)，比如说$gcd(7,10)=1$

互质的几何意义，如果 a 和 b 互质，这就意味着分数 a / b 已经不能再约分了，意味着 a × b 的棋盘的对角线不会经过中间的任何交叉点，意味着循环长度分别为 a 和 b 的两个周期性事件一同上演，则新的循环长度最短为 a × b 。

1.1.3 最大公约数一般使用欧几里得碾压相除法(Euclidean algorithm)计算

欧几里得算法使用了如下递归式

$gcd(69,21)=3$的计算方法
$gcd(69,21)=gcd(21,6)=gcd(6,3)=3$

1.2 最小公倍数(Least Common Multiple)

$lcm(x,y)$表示x和y的最小公倍数,例如$lcm(45,30)=90$

1.3 模运算

1.3.1 $xmodn$ 是$x$除以$n$的余数,例如$13mod5=3$

1.3.2 模运算符合交换律，结合律和分配律

1.3.3 如何计算$a^{x}modn$

如果$x$是2的幂次方，例如16，那么 $a^{16}modn=(((a^{2}modn{)}^{2}modn{)}^{2}modn{)}^{2}modn$
如果$x$不是2的幂次方，例如$a^{25}modn$
$25=16+8+1=(2+1)\times 2\times 2\times 2+1$
$a^{25}=a^{(2+1)\times 2\times 2\times 2+1}=(((a^2\times a{)}^2{)}^2{)}^2\times a$
$a^{25}modn=(((((((a^{2}modn)\times a)modn{)}^{2}modn{)}^{2}modn{)}^{2}modn)\times a)modn$

1.4 同余等式

如果$a$和$b$除$n$的余数相同，那么记为$a\equiv b(\mathrm{mod}n)$ 如果$a\equiv b(\mathrm{mod}n)$，那么$b\equiv a(\mathrm{mod}n)$ 如果$a\equiv b(\mathrm{mod}n),b\equiv c(\mathrm{mod}n)$，那么记为$a\equiv b\equiv a(\mathrm{mod}n)$ 如果$a_1\equiv b_1(\mathrm{mod}m),a_2\equiv b_2(\mathrm{mod}m),\dots ,a_n\equiv b_n(\mathrm{mod}m)$，那么

2.中国剩余定理

2.1 孙子算经中的问题

“今有物，不知其数。三、三数之，剩二；五、五数之，剩三；七、七数之，剩二。问物几何？答曰：二十三。”
《孙子算经》卷下第二十六问

2.2 数学解释

有$m$个两两互质的数，其乘积为$P$，有一个未知数$M$，如果我们已知$M$分别除以这$m$个数所得的余数，那么在0到$P–1$的范围内，我们可以唯一地确定这个$M$

2.3 直觉

两个除数的情况为例，假设两个除数分别是 4 和 7。下表显示的就是各自然数除以 4 和除以 7 的余数情况

可以看出，$imod4,imod7$的结果以$4\times 7=28$长度循环，每种特性的组合都在这28个结果中出现，所以一旦确定$imod4$和$imod7$的余数，就一定能唯一判定出$i$

2.4 数学表达

已知$m_1,m_2,\dots ,m_k$是两两互质的正整数，有未知数$x$满足同余方程组

那么

其中$M=m_1\cdot m_2\cdot \dots \cdot m_k,M_i=M/m_i$, 而$M_i^{-1}$是$M_i$的逆元（见3.3节），也就是$M_i{M}_i^{-1}\equiv 1(\mathrm{mod}{m}_i)$

2.5 举例，孙子算经中的问题

$m_1=3,m_2=5,m_3=7,a_1=2,a_2=3,a_3=2$，那么

3.欧拉定理

3.1 欧拉函数

任意给定正整数$n$，小于等于$n$的正整数之中，与n构成互质关系的数的个数记为$\varphi (n)$

如果$p$是质数，那么$\varphi (p)=p-1$， $\varphi (p^k)=p^k-p^{k-1}$
如果$n=pq,\varphi (n)=\varphi (p)\varphi (q)=(p-1)(q-1)$
如果$n=p_1^{k1}{p}_2^{k2}\dots p_r^{kr}$，那么

比如$\varphi (1323)=\varphi (3^3\times 7^2)=1323(1-\frac{1}{3})(1-\frac{1}{7})=756$

3.2 欧拉定理

如果$a$和$n$互质，那么

3.2.1

$\varphi (10)=4$，$7^{\varphi (10)}\equiv 7^4\equiv 2401\equiv 1(\mathrm{mod}10)$

3.2.2

$7^{4k}\equiv (7^4{)}^k\equiv \underset{\text{k}}{\underbrace{7^4\times 7^4\times \dots \times 7^4}}\equiv \underset{\text{k}}{\underbrace{1\times 1\times \dots \times 1}}(\mathrm{mod}n)$，所以$7^{4k}$尾数一定是1

3.2.3

由于$7^{4k}\equiv 1(\mathrm{mod}10),7^2\equiv 9(\mathrm{mod}10)$, 所以$7^{222}\equiv 7^{4\times 55+2}\equiv (\underset{55}{\underbrace{1\times 1\times \dots \times 1}}\times 9)(\mathrm{mod}10)$，所以$7^{222}$尾数为9

3.3 模反元素（逆元）

如果$a$和$n$互质，那么$ax\equiv 1(\mathrm{mod}n)$有解，$x$称为$a$模$n$的模反元素

3.3.1

用欧拉定理证明$a^{\varphi (n)}\equiv a\times a^{\varphi (n)-1}\equiv 1(\mathrm{mod}n)$，所以$a^{\varphi (n)-1}+kn$都是a的模反元素

3.3.2

例如求解同余方程$3x\equiv 1(\mathrm{mod}11)$，那么$3^{\varphi (11)-1}\equiv 3^9\equiv 19683\equiv 4(\mathrm{mod}11)$，所以$4+11k$都是同余方程的解

3.4 费马小定理

根据欧拉定理，当$p$是一个质数时，对于任意正整数$a$，有$a^p\equiv a(\mathrm{mod}p)$，如果$p\nmid a$，那么

4.扩展碾压相除法

4.1 裴蜀定理

对于方程$ax+by=d$，当且仅当$gcd(a,b)\mid d$时，方程有整数解

4.2 算法实现

对于方程$ax+by=gcd(a,b)$, 假设方程$bx+(amodb)y=gcd(a,amodb)$有整数解$(x^{\prime },y^{\prime })$，由于$gcd(a,b)=gcd(b,amodb)$,可以得到

所以

用递归算法实现

pair<int,int> exgcd(int a,int b){
    if(b == 0)return make_pair(1,0);
    pair<int,int>temp = exgcd(b,a%b);
    pair<int,int>ans = make_pair(temp.second,temp.first-(int)(a/b)*temp.second);
    return ans;
}