前言

前言同群论的前言，不管了，看的是初等数论。

第一章 整数理论

第1节 自然数、整除

• 自然数定义：显然在小学阶段我们就学过自然数的定义了，这里给出更加完整的定义。

  自然数集合N被定义：一种运算，称之为“后继”。该集合的每个元素都满足这种后继关系，这样的元素的集合称为自然数集合。

• 整除的定义：显然大家是知道的。

  设a,b为整数，b不等于0，若存在整数c，使a=bc，则称b可整除a，记作b|a（a除以b的余数为0）。不然，就称b不可整除a。当b可整除a时，称b为a的除数（或因数，约数），a是b的倍数，以及c是b除a所得的商。

• 公因数数的定义：显然这个也是大家都知道的。

  如果 d|a、且d|b， 那么称d为a、b的公因数。记d = GCD(a,b)

• 最大公因数与最小公倍数：使用gcd表示最大公因数，使用lcm表示最小公倍数。

  $ab=gcd(a,b)\times lcm(a,b)$

• 互质的定义：如果 GCD(a, b) = 1，那么a、b互质

• 质数定义：若a仅有 1和a($1\neq a$)两个因数，则称a是一质数。

 下面是关于整数的基本性质：

• 若能整除，商唯一。$a=bc_1,a=bc_2\rightarrow bc_1=bc_2.\because b\neq 0,\therefore c_1=c_2$
• 若$b|a,a|c$，则有$b|c$
• $b\neq0$的所有倍数为：$0,\pm b,\pm 2b,\pm 3b,...$
• $a\neq 0$，若 $b|a$，则 $|b| \le|a|$，等号当且仅当$b=\pm a$时成立。$a(\neq 0)$ 的除数只有有限个，a和-a的除数相同。$\pm1, \pm a$是a的显然除数

第2节 数学归纳法

• 归纳原理：设S是N的一个子集，如果下面两个条件成立，那么S=N

  • 条件1，$1\in S$
  • 条件2，如果$n\in S$，则$n+1\in S$

• 数学归纳法：设P(n)是关于自然数n的一种性质或命题，如果下面两个条件成立，那么P(n)对所有自然数n成立

  • 条件1，当n=1时，P(1)成立
  • 条件2，由P(n)成立必可推出P(n+1)成立

  证明：设使P(n)成立的所有自然数n组成的集合时S，S是N的子集，由条件1知$1\in S$；由条件2可知，若$n\in S$，则$n+1\in S$，所以由归纳原理知$S=N$。证毕

• 第二种数学归纳法：设P(n)是关于自然数n的一种性质或命题，如果下面两个条件成立，那么P(n)对所有自然数n成立

  • 条件1，当n=1时，P(1)成立
  • 条件2，对n>1，若所有的自然数 m<n，P(m)成立，则必可推出P(n)成立

  证明：反证法，若定理不成立，设T是使P(n)不成立的所有自然数组成的集合，T非空。集合T必有最小自然数t。由于P(1)成立，所以t>1。由条件2(取n=t时)可知，必有自然数m<t使得P(m)不成立。由T的定义可知$m\in T$，但这和t的最小性矛盾。证毕。

第3节 同余定理

• 同余定义：设a、b为两个整数，m是正整数，若 m 是 a-b 的因数，则称 a与b关于模m同余，记为 $a\equiv b(\mod m)$。

  我们把这个公式写一下，相当于 $\frac{a-b}{m} = k$、$a=km+b$、$(a-b) \mod m = 0（或 m|(a-b)）$，即$a\mod m = b\mod m$

  并且有$(a-b)/m=k \rightarrow a=km+b$

  同余类：所有和a模m同余的整数集称为a模m的同余类

  • $a\equiv b(\mod m)\rightarrow da \equiv db(\mod m)$
  • $a\equiv b(\mod m),\quad c\equiv d(\mod m)\rightarrow (a+c)\equiv (b+d)(\mod m)$
  • $a\equiv b(\mod m),\quad c\equiv d(\mod m)\rightarrow ac\equiv bd(\mod m)$

• 如果$a\equiv b(\mod m), c\equiv d(\mod m)$，那么$a+c\equiv b+d(\mod m)$并且$ac\equiv bd(\mod m)$

  证明：

  $b=a+sm, d=c+tm$

  $b+d=(a+sm)+(c+tm) =(a+c)+m(s+t)$

  $bd = (a+sm)(c+tm) = ac + m(at+sc+stm)$

• $(a+b)\mod m = ((a\mod m)+(b\mod m))\mod m$且$ab\mod m = ((a\mod m)(b\mod m))\mod m$

  证明：

  $\because a\equiv (a\mod m)\mod m, b\equiv (b\mod m)\mod m$

  $\therefore a+b\equiv ((a\mod m)+(b\mod m) )\mod m$

  $ab \equiv ((a\mod m)(b\mod m))\mod m$

• $a\equiv 1(\mod m)\rightarrow a^k\equiv 1(\mod m)$

  证明：$a = dm+1$，$a^k = (dm+1)^k = \sum\limits_{i=0}^k C_n^i (km)^i = 1+\sum\limits_{i=1}^n C_n^i(km)^i$

  其中，后面那项是可以被m整除的，只剩下1了，所以原式得证

第二章 模运算

第1节 二进制

 相信阅读本文的读者，对于二进制应该不陌生，这里仅仅快速提两句。假设数字 $a=(a_{n-1}a_{n-2}...a_2a_1a_0)_2$用二进制表示是这样，那么在10进制的计算中有$a=a_{n-1}\times 2^{n-1} + a_{n-2}\times 2^{n-2} + ...+ a_2\times 2^2 + a_1 \times 2^1 + a_0 \times 2^0$，其中，$a_i = 0\ \ or\ \ 1, 0\leq i \leq n-1$。

第2节 模指数运算

 设想计算 $b^n \mod m$的结果，第一反应肯定是把乘以n个b之后然后对m取模，倘若b n m都非常大，那么在计算机中想要计算又该如何呢？接下来介绍在计算机中这个式子应该如何化解，假设 $n=(a_{n-1}a_{n-2}...a_2a_1a_0)_2$，那么在十进制中有 $n=a_{n-1}\times 2^{n-1} + a_{n-2}\times 2^{n-2} + ...+ a_2\times 2^2 + a_1 \times 2^1 + a_0 \times 2^0$，进而有

$$b^n = b^{a_{n-1}\times 2^{n-1} + a_{n-2}\times 2^{n-2} + ...+ a_2\times 2^2 + a_1 \times 2^1 + a_0 \times 2^0} \\ = b^{a_{n-1}2^{n-1}} \times b^{a_{n-2}2^{n-2}} \times...\times b^{a_12^1}\times b^{a_02^0} \\ = b^{a_0} \times (b^{2})^{a_1} \times (b^4)^{a_2} \times ...$$

其中，可以去除掉$a_j = 0$的项，剩下$a_i = 1$的项。

 而且，值得注意的是，假设$a_2=1$，那么第三项其实只是变为$(b^4)^1 = b^4$，所以对于第三项最终我们的任务会落在如何快速求解$b^4\mod m$上来。

 对于第一项，也就是$i=0$时，$b^{a_0}=1$。自然可以忽略掉，因此我们把目光放到后面n-1项。后面的项，则可以根据[第一章第3节](# 第3节 模)的公式计算。假设后面剩了m项，每一项的指数都是2的几次方的。对于$b^{2^i}\mod m$快速算法可以看下面。因此我们假设剩下$b^n = 1b_1 b_2 b_3$剩下了任意的三项。就可以这么计算，把$b_1b_2b_3$看作一个整体，进行模运算。得到结果$e_1$（$e_1 < m$），再把结果和$b_1$相乘后，看作整体依次往后算。

 容易求得$b\mod m=c$。其次，对于$b^2 \mod m = (b\times b) \mod m = ((b\mod m )\times (b\mod m))\mod m$，其中$b\mod m$已经求出了，带入即可。$b^2 \mod m = c^2 \mod m=c_2$。可能要说了，好像没什么变化啊，无非是把b换成c了。但是，值得注意的是b的大小可能比m大，也可能比它小。而c的大小一定比m小。这样就不会超出了，对于$b^4=(b^2 \times b^2)\mod m= ((b^2\mod m) \times (b^2\mod m))\mod m = c_2^2 \mod m = c_4$，以此类推。下面给出伪代码和C++代码。

 该算法的时间复杂度为：$O((\log\ m)^2\log\ n)$次的二进制位运算，注意是位运算。

function b n m
	e = 1
	power = b mod m
	for i=0 to n-1
		if ai = 1 then e = (e * power) mod m
		power = (power * power) mod m
	return e

// 快速计算 b^n mod m
long long power_mod(long long b, long long n, long long m){
    long long e = 1;
    long long power = b % m;
	while(n){
        if(n & 0x1){
            e = (e * power) % m;
        }
        power = (power * power) % m;
        n >>= 1;
    }
    return e;
}

第三章 质数

• 每个大于1的整数都可以唯一地写成两个或更多个素数的乘积，其中素数因子已非递减序排列。

• 如果n是一个合数，那么n必有一个素数因子小于或等于$\sqrt{n}$。

• 埃拉托斯特尼筛选法：

  1. 列出从1~n的所有整数
  2. 找到所有不超过$\sqrt{n}$的素数，共m个
  3. 依次去除n以内能被这m个素数整除的整数
  4. 剩下的就是素数了

• 素数具有无限个，假如素数有限，所有素数的乘积再+1，一定是一个素数。所以又会存在更多的素数。

  下面来证明为什么所有素数的乘积再+1仍然是素数，假设所有素数的集合表示为a，共n个

  令$q=a_1a_2a_3...a_n$，如果q+1不是素数，那么其一定有一个因子$a_0 \in a$。

  $\frac{q+1}{a_0} = \frac{a_1a_2a_3...a_n}{a_0} + \frac{1}{a_0}$，右边的第一项是整数，但是第二项一定是小数，所以不能被整除。

• 素数定理：当x无限增大时，不超过x的素数个数与$x/\ln x$之比趋近于1。

• 孪生素数：相差为2的一对素数，如3和5，5和7。

• 辗转相除法：如何求解两个大整数的gcd呢？假设大的那个数字是a，小的那个数字是b

  $gcd(a,b) = gcd(a-b, b)$，同样缩小规模，证明方法同上。不过是c变成了a-b而已。

• 贝祖（裴蜀）定理：如果a和b是正整数，必定存在整数s和t，使得$gcd(a, b) = sa+tb$。证明请看：oi-wiki 裴蜀定理

  请看后面的扩展欧几里得算法

  除此之外，对这个式子做一个扩展，$ax+by=m$有整数解，需要g(a,b)|m

• 如果a,b,c为正整数，使得gcd(a,b)=1且a|bc，那么a|c

  证明：$sa+tb = 1\rightarrow sac+tbc=c$，

  $a|bc\rightarrow a|tbc, a|sac \rightarrow a|(tbc+sac) \rightarrow a|c$

• 如果p是素数，且$p|a_1a_2\dots a_n$，其中$a_i$为整数，对于某个i，$p|a_i$

• 令m为正整数，令a，b，c为整数。如果$ac\equiv bc(\mod m)且gcd(c,m) = 1$，那么$a\equiv b(\mod m)$。

第四章 同余方程

第1节 引言

 形如$ax\equiv b(\mod m)$的线性方程称之为同余方程。其中，m是正整数，a，b是整数，x是变量。怎么求解线性同余方程呢？即，如何找到所有满足该方程的整数x。接下来介绍一个方法是：$\overline a a\equiv 1(\mod m)$，如果这样的整数存在，称$\overline a$为a模m的逆元或逆。

第2节 定理

• 如果a和m互素，且m>1，则a模m的逆存在，且这个模m的逆时唯一的。

  $\because gcd(a,m) = 1,\quad \exist s,t\ \ \ sa+tm=1\rightarrow sa+tm\equiv 1(\mod m)$

  $\because tm\equiv 0(\mod m)\therefore sa\equiv 1(\mod m)$

  下面来证明唯一性：

• 中国同余定理：$x\equiv a_i(\mod m_i)\quad 1\leq i\leq n$，共有n个同余式使得x均成立，求解x。

  $m_1,m_2,\dots,m_n$为大于1的两两互素的正整数，而$a_1,a_2,\dots,a_n$是任意整数，那么这个方程组有唯一的模$m=m_1m_2\dots m_n$的解。（即，存在一个满足$0\leq x \leq m$的解x，而所有其他的解均与此解模m同余）

  证明存在：

  设$M_i = m/m_i, 1\leq i\leq n$，那么显然会有$gcd(M_i, m_i) = 1$，所以$M_iy_i\equiv 1(\mod m_i)$存在唯一解。

  要构造满足所有方程的解，求和$x = \sum\limits_{i=1}^n a_iM_iy_i$

  • 当$i\neq k$时，$M_i \equiv 0(\mod m_k)$
  • 当$i=k$时，$M_ky_k \equiv 1(mod m_k)\rightarrow a_kM_ky_k\equiv a_k(\mod m)$

  综合前面两个，所以x是$x\equiv a_k(\mod m_k)$的解

• 假设$m_1, m_2,\dots,m_n$是两两互素的模数，并令m为其乘积。根据剩余定理可以证明满足$0\leq a< m$的整数a可以唯一表示成一个n元组，即$(a\mod m_1, a\mod m_2,\dots, a\mod m_n)$，这在计算机上的大整数计算非常适用，并且还能并行处理加快速度。

  例如，存在n个模数$m_i, 1\leq i \leq n$，存在两个非常大的数字$N_1,N_2$，那么这两个大数可以分别表示为：

  N_1:\{N_1\mod m_i|(1\leq i\leq n) \and i\in Z\} = (n_{11}, n_{21},...,n_{n1})，N_2:\{N_2\mod m_i|(1\leq i\leq n) \and i\in Z\} = (n_{12}, n_{22}, ... , n_{n2})

  那么有$N_1 + N_2 = \{(n_{11}+n_{12})\mod m, ..., (n_{n1}+n_{n2})\mod m\} = {n_1,n_2, ...,n_n}$

  如何还原成大整数呢？

  即求解同余方程组 $x\equiv n_i(\mod m_i), 1\leq i\leq n$

• 费马小定理：如果p为素数，a是一个不能被p整除的整数，则$a^{p-1} \equiv 1(\mod p)$，对每个整数a都有$a^p \equiv a(\mod p)$

• 欧拉定理：对费马小定理的扩展，若$gcd(a,m)=1$，那么$a^{\phi(n)}\equiv1(\mod m)$，其中$\phi(n)$为欧拉函数。当n为素数时，$\phi(n)=n-1$，就是费马小定理。

• 伪素数：b是一个正整数，n是一个正合数且$b^{n-1} \equiv 1(\mod n)$，则称n为以b为基数的伪素数

• 一个正合数n如果对于所有满足$gcd(b, n)=1$的正整https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95数b都有同余式$b^{n-1} \equiv 1(\mod n)$成立，则称为卡米切尔数。

• 模素数p的一个原根是$Z_p$中的整数r使得$Z_p$中的每个非零元素都是r的一个幂次（$Z_p$表示小于p的非负整数集合）

  详细说来，如果a是p的原根，那么有集合$Z'=\{ (a^i\mod p) | 1\leq i < p, i\in Z\} = (a^1\mod p, a^2\mod p,...,a^{p-1}\mod p)$

  则需要集合$Z'$与集合$Z_p$相等，a就是p的原根

• 离散对数：假设p是一个素数，r是一个模p的原根，而a满足[1, p-1)之间的一个整数。如果$r^e\mod p = a且 0\leq e\leq p-1$，我们说e是以r为底a模p的离散对数，并写作$\log_r a = e$（这式子是跟p有关的，但是式子中没有表现出来）

  比如，找出以2为底3和5模11的离散对数，已知$2^8\mod 11 =3和2^4\mod 11 = 5$，那么有$\log_23 = 8和\log_25=4$

第3节 求解线性同余方程

$ax\equiv b(\mod m)$

同理，该方程可以化成 $\frac{ax-b}{m} = d$，进而化解成$ax+km=b$，其中k、d为未知数，且k=-d，a、b、m是已知数，那么就相当于求解满足要求的x和k，相当于不定方程，或者相当于直线点集。

• 求解逆元的几种方法：https://oi-wiki.org/math/number-theory/inverse/

  • 扩展欧几里得法：$sa+tb=gcd(a,b)=1$，用扩展欧几里得算法求出s和t即可。

  • 费马小定理/欧拉定理：$aa^{p-2} \equiv 1(\mod n)$或者$aa^{\phi(n)-1} \equiv 1(\mod n)$。

  • 递推法求逆元：依次求出1，2，…，a关于n的逆元。也就是依次求出，$i^{-1}$来即可，满足$ii^{-1}\equiv 1(\mod n)$。

    如果i=1，那么显然$i^{-1}\equiv 1(\mod n)$

    如果i>1，令$n=ki+j，k=\lfloor \frac{n}{i}\rfloor, j=n\mod i$，并且改写成$(\mod n)$的形式

    $ki+j\equiv 0(\mod n)$，两边乘以$i^{-1}\times j^{-1}$

    $kj^{-1}+i^{-1}\equiv 0(\mod n)$

    $i^{-1}\equiv -kj^{-1} \equiv -\lfloor \frac{n}{i}\rfloor j^{-1} \equiv(\mod n)$

    其中，会发现$j=n\mod i < i$，而在求$i^{-1}$之前，我们已经求了所有小于i的逆元，其中也包括j的逆元。

    请看下面的C++代码，摘自OI-WIKI

// 递推法求逆元
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}
// 注意inv[0]没有定义，由于如果有i|p的情况出现，此时就不存在i的逆元
// 再看到我们用了p-p/i，防止负数出现

• 求解线性同余方程：https://oi-wiki.org/math/number-theory/linear-equation/
  • 扩展欧几里得：$ax\equiv b(\mod m)\rightarrow ax+tm=b$，如果$gcd(a,m)|b$的话，即可用。

第4节 扩展欧几里得算法

• 欧几里得算法：又叫做辗转相除法，如何求解两个大整数的gcd呢？假设大的那个数字是a，小的那个数字是b

  求$gcd(a,b)$先求$c = a \mod b$，然后再求$gcd(b,c)$，这时一定有$c < b$。并且问题已经转换到$gcd(a,b) = gcd(b, c)$了，数字已经变小了，继续缩小数字，直到能够求解出来。

  证明：现在其实只需要证明一下$gcd(a,b)=gcd(b,c)$，首先我们有$a = bk+c$。

  1. 设m是a与b的任意的公约数，$a = md_1, b = md_2 \rightarrow c = a-bk = md_1-md_2k=m(d_1-d_2k)$，所以m也是c的约数
  2. 设n是b与c的任意的公约数，$b=nh_1, c=nh_2\rightarrow a =bk+c = nh_1k+nh_2 = n(h_1k+h_2)$，所以n也是a的约数

  结合1和2，abc三个数的公约数相等，所以这三个数的最大公约数也是一样的。

下面用数学的式子给出其步骤吧：记$a=r_0, b=r_1$，由上述证明可以知道$gcd(r_i, r_{i+1}) = gcd(r_{i+1}, r_{i+2})$，对任意i均成立。

$r_0 = k_1 r_1 + r_2$，$r_1 = k_2r_2+r_3$，…，$r_i=k_{i+1}r_{i+1}+r_{i+2}$，…，直到$r_{i+2}=0$，算法就可以停止了，最终结果便是$gcd(a,b) = gcd(r_{i}, r_{i+1})=r_{i+1}$。

• 扩展欧几里得算法：在欧几里得的算法进行扩展，并且可以求得$sa+tb=gcd(a,b)$中的s和t

  在欧几里得的基础上，加上两个量，一个是$s_i$，一个是$t_i$，并且有$s_0=1,s_1=0,t_0=0,t_1=1$。然后每一步都有的运算均与$r_i$一样，终止结果也是一样的。

  同样，记$a=r_0, b=r_1$。直接写出每一步的通式：$r_i=k_{i+1}r_{i+1}+r_{i+2},\quad s_i=k_{i+1}s_{i+1}+s_{i+2},\quad t_i=k_{i+1}t_{i+1}+t_{i+2}$。注意，其中$k$都是一样的。

  我们知道$gcd(a,b)=r_{i+1}$，那么有$s=s_{i+1}, t=t_{i+1}$

  如何证明呢？

第五章 同余应用

• 散列函数：散列函数中最简单的就是取余的散列函数了，如果同余的话，那么就会发生散列碰撞了。
• 伪随机数：常用的伪随机数是：$x_{n+1} = (ax_n+c)\mod m$
• 检验码：奇偶校验位常用模2来检测，也就是最终检测$res\equiv1(\mod n)$