浅谈数论

前言

若非特殊说明，本文所有的未知数均为整数

符号

1. $\lfloor x \rfloor 、\lceil x \rceil$ x向下取整、向上取整

   定义：

   • $\lfloor x \rfloor:小于等于x的最大整数$

   • $\lceil x \rceil:大于等于x的最小整数$

   性质：$\lfloor x \rfloor = - \lceil -x \rceil$

2. $a \% b = c$ 也写成$a \bmod b = c$ 即$c$是$a+kb$的最小正值

   注：这个定义虽然当$b \leqslant 0$时也成立，但一般不考虑该情况，当$b \gt 0$时，$a \% b \Longleftrightarrow a - \lfloor\frac{a}{b}\rfloor \times b$。

   性质：

   • $(a + b)\bmod c = ((a \bmod c) + (b \bmod c))\bmod c$

   • $(a \times b)\bmod c = ((a \bmod c) \times (b \bmod c))\bmod c$

   • $a^b \bmod c =(a \bmod c)^b \bmod c$

3. $\text{gcd}(a,b)=c \quad$即整数a,b的最大公约数是c

   当$\text{gcd}(a,b)=1$时，称a，b互质。

   性质：

   1. $\text{gcd}(a,b)=\text{gcd}(b,a)$
   2. $\text{gcd}(a,0)=a$
   3. $\text{gcd}(a,b)=\text{gcd}(b,a\%b)$
   4. 裴蜀定理：$\text{gcd}(a,b) 是集合 \{ax+by|x,y \in \mathbb{Z}\} 中最小的正整数$
   5. 4的推论：$整数线性组合ax+by的值恰为 \text{gcd}(a,b)的所有倍数$

   根据性质3求$\text{gcd}(a,b)$的时间复杂度最坏是$O(\log _{\phi} \min(a,b))$,一般计为$O(\log min(a,b))$

   性质3的证明：

   $$设r=x\%y,k=\frac{x-r}{y}\\ 则r=x-ky,x=r+ky\\ 一方面：设d为x,y的公约数，x=l\cdot d,y=m\cdot d\\ \therefore r=x-ky=l\cdot d-k\cdot md=(l-k\cdot m)d\\ \therefore d为md,(l-km)d的公约数\\ \therefore d为y,r的公约数\\ 另一方面：设q为y,r的公约数，y=o\cdot q,r=p\cdot q\\ \therefore x=r+ky=p\cdot q+k\cdot oq=(p+k\cdot o)q\\ \therefore q为(p+ko)q,oq的公约数\\ \therefore q为x,y的公约数\\ \therefore (d是x,y的公约数)是(d是y,r的公约数)的充分必要条件\\ \therefore x,y的公约数集合A\{d|(d\mid \text{gcd}(x,y) )\}等价于y,r的公约数集合B\{q|(q \mid \text{gcd}(y,r))\}\\ \therefore \text{gcd}(x,y)=gcd(y,r)\\ 证毕$$

4. $\text{lcm}(a,b)=c\;$ 即c是a、b的最小公倍数

   性质：$\text{lcm}(a,b)=\frac{ab}{\text{gcd(a,b)}}$

5. $a \mid b$ 读作$a整除b$ 即**$a是b的因数$**

   特别的，$a\mid 0,1 \mid a$

   性质：

   1. 若$a \mid b ,c \mid b且a,c互质,则 ac \mid b$

   2. z若$a \mid b,a \mid c \Longleftrightarrow \forall x,y \ a\mid (bx+cy)$

      证明：

      $$\because a \mid b, a \mid c \\ \therefore a \mid \text{gcd}(b,c) \\ \therefore a \mid k \cdot \text{gcd}(b,c) \\ \therefore a \mid (bx+cy)$$

6. $a\equiv b \pmod c \;$ ：$a,b模c同余$，即$a\% c = b \% c$

   意义：

   $a\equiv b \pmod c$表明a,b模c的意义一样

   举例:

   $$求：{({999}^{999})}^{999}\bmod 1000\\ \because (-1) \equiv 999 \pmod {1000}\\ \therefore {({999}^{999})}^{999}\bmod 1000 \Longleftrightarrow [(-1)^{(-1)}]^{(-1)} \bmod 1000 = (-1) \bmod 1000 =999$$

   性质：

   • $(a \% m + b \% m) \% m = (a+b)\%m$
   • $(a \% m - b \% m) \% m = (a-b)\%m$
   • $(a \% m \times b \% m) \% m = (a \times b)\%m$
   • 若$a\equiv b \pmod c \Longleftrightarrow c \mid (a-b)$

   如果你只知道$a\%m,b\%m$的值可以进行三则运算推出$(a+b)\% m,(a-b)\% m,(a\times b)\% m$的正确值

   这里没有除法运算，假如你只知道$a\%m,b\%m$的值，无法通过$\frac{a\%m}{b\%m}$来计算$\frac{a}{b} \% m$的值，但还有其他方法来计算（后文会将具体处理方法）

---

正文

引例

1. 求$999^{999^{999}} \bmod 1000$
2. 出以下方程未知数的通解或说明其无解

   1. $3x \equiv 1 \pmod {9}$

   2. $3x \equiv 2 \pmod 8$

3. 正整数，除以三余二，除以五余二，除以七余三，问这个数最小是多少？
4. 已知一个大于$1000$的数末三位是$123$，把该数乘了一个正整数$x$，现在它的末三位为$041$，问乘的数$x$最小是多少？
5. 已知一个大于$1000$的数末三位是$201$，把该数乘了一个正整数$x$，现在它的末三位为$067$，问乘的数$x$最小是多少？
6. 是否存在21个连续的正整数，使得其中每个数均被至少一个$2 \sim 13$ 的素数整除？若有，请写出这21个正整数的中间数的最小值；若没有，请说明理由。
7. 计算$7^{105} \bmod 10$
8. $1032^{1032} 的最后两位？$
9. 定义$\begin{cases}f(1)=1 \\当n为正整数时\quad f(n)=n^{f(n-1)} \end{cases}$,求$f(2008)$的最后3位。
10. 求证：当$n\geqslant 3$时，$n^{(n^{n})}\equiv n^{n} \pmod {16}$
11. 求证：当$n\geqslant 3$时，$1989 \mid n^{(n^{(n^{n})})}-n^{(n^{n})}$
12. 试证明非对称加密算法$RSA$算法的正确性并解释

扩展欧几里得定理

明确定义

扩展欧几里得定理(Extended Euclidean algorithm、EXGCD) 是一个用来求解形如$ax\equiv b \pmod c$的线性同余方程的整数解的算法

转化

若想求解形如$ax\equiv b \pmod c$的方程的通解或判断是否有解，不妨根据同余的性质，使原方程等价于$ax+cy=b$

接下来我们求解x,y即可

(我们不需要考虑$a,c,b \lt 0$时的情况，因为我们可以将方程变为$|a|(\frac{a}{|a|}\times x)+|c|(\frac{c}{|c|}\times y)=b$的形式)

通解公式

我们先不研究该方程的解，我们研究该方程解的性质：

$$若x_1,y_1是方程ax+cy=b的一组解\\ 则ax_1+cy_1=b\\ \therefore ax_1+a\cdot c\cdot k - a\cdot c \cdot k + cy_1=b\\ \therefore a(x_1+c\times k)+c(y_1-a\times k) =b\\ \therefore 该方程的所有解为\begin{cases} x=x_1+c\times k\\ y=y_1-a\times k \end{cases}$$

接下来只需要求解该方程的一组解即可

化简

我们不妨令$a^\prime =\frac{a}{\text{gcd}(a,c)},b^\prime =\frac{b}{\text{gcd}(a,c)},c^\prime =\frac{c}{\text{gcd}(a,c)}$则方程$ax+cy=b$ 可以变形为$a^\prime x+c^\prime y=b^\prime$

显然的$a^\prime,c^\prime \in \mathbb{Z}\ ,\text{gcd}(a^\prime ,c^\prime )=1$

根据$gcd$的性质，$a^\prime x+c^\prime y可以表示为整数k \times gcd(a^\prime ,c^\prime)=k\times 1=k$

$\therefore a^\prime x+c^\prime y\in \mathbb{Z}$

若$b^\prime \notin \mathbb{Z},则a^\prime x+c^\prime y \notin \mathbb{Z},与上文矛盾。$

$所以,方程ax+cy=b有解,当且仅当\text{gcd}(a,c)\mid b$

接下来只需要求解方程$a^\prime x+c^\prime y= b^\prime$

随堂测验：请写出下列方程的通解或说明其无解:

2. $3x\equiv 1 \pmod 9$

   解：

   $$该方程等价于3x+9y=1\\ 提取a,b的最大公约数3,方程变为3(x+3y)=1\\ \because 3 \nmid 1\\ \therefore 该方程无解$$

3. 化简：$12x+4y=8$

   解：$3x+y=2$

再变形

方程变为了$ax+by=c$ (注此时的a，$b$和上面不同，并且$\text{gcd}(a,b)=1$)

我们不妨研究方程 $aX+bY=1$中$x,X,y,Y$的关系

将方程二两边乘以$c$，变为 $a(X\cdot c)+b(Y\cdot c)=c$

接下来只需要解出方程$aX+bY=1$并且满足 $\text{gcd}(a,b)=1$的解$X,Y$然后再同时$\times c$即可

求解

$$\because aX+bY=1,\text{gcd}(a,b)=1\\ \therefore aX+bY=\text{gcd}(a,b)\\ 我们不妨多列几个形如这样的方程,然后令下一层的a等于上一层的b，下一层的a等于上一层的a取模上一层的b\\ 一直列下去，总有一层的b会等于0，求解出最后一层的X,Y，再寻找现相邻两层X,Y的关系即可\\ （注：我这里会用下标表示层数）\\ 举例： 133X+403Y=1\\ 403X_1+133Y_1 =1\\ 133X_2+4Y_2=1\\ 4X_3+Y_3=1\\ X_3+0\cdot Y_3=1\\ 解得X_3=1,Y_3为任意整数，令Y_3=0$$ $$接下来我们研究X_n与X_{n+1} ，Y_n与Y_{n+1} 的关系\\ 对于X_n,Y_n,有aX_n+bY_n=1\\ 对于X_{n+1} ,Y_{n+1} ，有bX_{n+1} +(a\%b)Y_{n+1} =1\\ \therefore aX_n+bY_n=bX_{n+1}+(a\%b)Y_{n+1}\\ 因为a,b大于0，所以根据余数的性质，原式变为aX_n+bY_n=bX_{n+1} +(a-\lfloor\frac{a}{b}\rfloor \times b)Y_{n+1}\\ aX_n+bY_n=bX_{n+1} +aY_{n+1}-\lfloor \frac{a}{b} \rfloor \times b Y_{n+1}\\ aX_n+bY_n= aY_{n+1}+ b(X_{n+1} -\lfloor \frac{a}{b} \rfloor \times Y_{n+1})\\ \therefore X_n=Y_{n+1},Y_n=X_{n+1}-Y_{n+1} \lfloor \frac{a}{b} \rfloor\\ 我们求解出最后一层的X,Y，然后拿这个公式反推出上一层的X,Y，一直推到第一层，就完事了！\\ 举例：\\ 266x\equiv4 \pmod {806}\\ 266x+806y=4\\ 133x+403y=2\\ 133X+403Y=1\\ 403Y_{1}+133Y_{1}=1\\ 133X_{2}+4Y_{2}=1\\ 4X_{3}+Y_{3}=1\\ X_{4}+0\cdot Y_{4}=1\\ X_{4}=1,Y_{4}=0\\ X_{3}=Y_{4}=0,Y_{3}=X_{4}-Y_{4}\times\lfloor\frac{4}{1}\rfloor=1-0\times 4=1\\ X_{2}=1,Y_{2}=-33\\ X_{1}=-33,Y_{1}=100\\ X=100,Y=-33\\ \begin{cases} x=X\times 2=200+403k\\ y=Y\times 2=-66-133k \end{cases}$$

小结

首先扩展欧几里得的运算过程与欧几里得算法的运算过程基本一致，所以求解$ax\equiv c \pmod b$的时间复杂度也是$O(\log \text{min}(a,b))$

1. 已知一个大于$1000$的数末三位是$123$，把该数乘了一个正整数$x$，现在它的末三位为$041$，问乘的数$x$最小是多少？

   $$根据题意，可以列出方程：\\ 123x\equiv41 \pmod {1000}\\ 123x+1000y=41\\ 123X+1000Y=1\\ 1000X^1+123Y^1=1\\ 123X^2+16Y^2=1\\ 16X^3+11Y^3=1\\ 11X^4+5Y^4=1\\ 5X^5+Y^5=1\\ X^6=1,Y^6=0\\ X^5=0,Y^5=1\\ X^4=1,Y^4=-2\\ X^3=-2,Y^3=3\\ X^2=3,Y^2=-23\\ X^1=-23,Y^1=187\\ X=187,Y=-23\\ \begin{cases} x=X\times 41=7667+1000k\\ y=Y\times 41=-943-1000k\\ \end{cases}\\ \because x \leqslant 1000\\ \therefore x=(7667+1000k)\%1000=667$$

2. 已知一个大于$1000$的数末三位是$603$，把该数乘了一个正整数$x$，现在它的末三位为$201$，问乘的数$x$最小是多少？

   $$根据题意，可以列出方程：\\ 201x\equiv67 \pmod {1000}\\ 201x+1000y=67\\ 201X+1000Y=1\\ 1000X^1+201Y^1=1\\ 201X^2+196Y^2=1\\ 196X^3+5Y^3=1\\ 5X^4+Y^4=1\\ X^5=1,Y^5=0\\ X^4=0,Y^4=1\\ X^3=1,Y^3=-39\\ X^2=-39,Y^2=40\\ X^1=40,Y^1=-199\\ X=-199,Y=40\\ \begin{cases} x=X\times 67=-13333+1000k\\ y=Y\times 67=2680-1000k\\ \end{cases}\\ \because x \leqslant 1000\\ \therefore x=(-13333+1000k)\%1000=667$$

代码实现

long long mod(long long a, long long m) { return (a % m) + m % m; }
void exgcd(long long & x, long long & y, long long a, long long b) {
  if (b == 0) {
    x = 1ll, y = 0ll;
    return;
  }
  exgcd(x, y, b, a % b);
  swap(x, y);
  y -= a / b * x;
}
tuple<pair<long long, long long>, pair<long long, long long>, bool> axbyc(long long a, long long b, long long c) {
  if (a < 0 && b < 0) {
    tuple<pair<long long , long long >, pair<long long , long long >, bool> result = axbyc(-a, -b, -c);
    return result;
  } else if (b < 0) {
    tuple<pair<long long, long long>, pair<long long, long long>, bool> result = axbyc(a, -b, c);
    get<1>(result).first = -get<1>(result).first;
    get<1>(result).second = -get<1>(result).second;
    return result;
  } else if (a < 0) {
    tuple<pair<long long, long long>, pair<long long, long long>, bool> result = axbyc(-a, b, c);
    get<0>(result).first = -get<0>(result).first;
    get<0>(result).second = -get<0>(result).second;
    return result;
  } else {
    ulong long temp = gcd(a, b);
    if (c % temp != 0) return {{0, 0}, {0, 0}, 0};
    a /= temp, b /= temp, c /= temp;
    long long x = 0, y = 0;
    exgcd(x, y, a, b);
    x *= c, y *= c;
    return {{x, b}, {y, -a}, 1};
  }
}
pair<long long, bool> SolveCongruenceEquation(long long a, long long b, long long mod) {  // ax ≡ b (mod)
  tuple<pair<long long, long long>, pair<long long, long long>, bool> result = axbyc(a, mod, b);
  if (get<2>(result) == 1) {
    pair<long long, long long> x = get<0>(result);
    return {Mod(x.first, x.second + x.second), 1};
  } else return {0, 0};
}

---

逆元

明确定义

在我们小学的时候，对实数a的倒数的定义是与相乘等于1的数，特别的，0没有倒数

令a的倒数为b，于是我们就可以用乘b来代替除以a的操作。

于是我们讨论在模意义下的倒数，也就是逆元

逆元的定义：满足$ax\equiv1 \pmod c$的整数x，称为a在模c意义下的逆元，计为模$c$下的$a^{-1}$

注意：有的时候逆元并不存在。

求解

根据逆元的定义，可以用扩展欧几里得算法求解，还可以用其他算法求解，下文会做补充。

求解$a$模$p$的逆元的时间复杂度与扩展欧几里得算法一致,$O(\log a)$

逆元的作用、意义

1. 已知一个大于$1000$的数末三位是$123$，小景把该数乘了一个正整数$x$，现在它的末三位为$041$，问她乘的数$x$最小是多少？
2. 已知一个大于$1000$的数末三位是$603$，小溪把该数乘了一个正整数$x$，现在它的末三位为$201$，问她乘的数$x$最小是多少？

没错，又是这两题。不知道你有没有发现，这两题的答案竟然是一样的。

仔细想想，第一题是要把123变为041，相当于除以三，第二题是要把603变为201，也是除以三，并且都是模1000意义下的。

不妨列出方程$3x\equiv1 \pmod {1000}$,解得x=667,于是我们便知道了，除以3跟乘667的意义一致。

然后用通解的公式，解出x的最小正值即可。再举一个例子：已知一个大于$1000$的数末三位是$900$，将该数乘了一个正整数$x$，现在它的末三位为$300$，问她乘的数$x$最小是多少？

$x=667 \% (\frac{1000}{\text{gcd}(900,1000)})=7$

我们不妨把问题抽象出来，并且建模：

$$有正整数A,B且B\mid A但是不知道他们的值，只知道他们模m的值a=A\%m,b=B\%m\\ 问(\frac{A}{B}) \% m的值?\\ 当\text{gcd}(b,m)=1时\\ 因为A|B,所以\frac{A}{B}为正整数，令C=\frac{A}{B},则C为正整数\\ \therefore A= BC \\ \therefore a\equiv bC \pmod m (①)\\ \because \text{gcd}(b,m)=1\\ \therefore b^{-1}在模m下存在\\ 将①两边乘b^{-1}， a b^{-1} \equiv b \times b^{-1} \times C \pmod m\\ \therefore ab^{-1}\equiv C \pmod m\\ \therefore (\frac{A}{B}) \bmod m = a\times b^{-1} \bmod m\\ 所以，我们证明了当\text{gcd}(b,m)=1时，(\frac{A}{B}) \% m=a\times b^{-1}\bmod m\\ 于是,我们得到了(\frac{A}{B}) \% m的通解:ab^{-1}+km,因为(\frac{A}{B}) \% m\lt m,所以这个答案变成唯一解ab^{-1}\\ ----------------------------------\\ 还没完，当\text{gcd}(b,m) \neq 1时\\ 设d=\text{gcd}(b,m)\\ \because a=A \bmod m, b= B \bmod m\\ \therefore A=a+xm,B=b+ym\\ 根据gcd的性质，因为b=B \bmod m,所以\text{gcd}(B,m)=\text{gcd}(b,m)=d,又因为A\mid B,\therefore \text{gcd}(A,m)=d\\ 设a^\prime =\frac{a}{d},b^\prime =\frac{b}{d},m^\prime = \frac{m}{d}\\ \therefore \frac{A}{B} \bmod m = \frac{a+xm}{b+ym} \bmod m =\frac{d\times (a^\prime+x\times m^\prime)}{d\times (b^\prime+y\times m^\prime)}=\frac{a^\prime+x\times m^\prime}{b^\prime+y\times m^\prime}\\ 令A^\prime =a^\prime +x\times m^\prime ,B^\prime =b^\prime +y\times m^\prime \\ 问题转换为\frac{A^\prime}{B^\prime} \bmod m^\prime ,并且此时B^\prime ,m^\prime 互质,随后参照情况一,会得到x_0+km^\prime 这一通解,但不同的是,这次是多解。$$

举例：

• $$a=3,b=4,m=5时\\ \because \text{gcd}(b,m)=1\\ \therefore 模m下b^{-1}=4\\ \therefore \frac{A}{B} \bmod m = a \times b^{-1} \bmod m= 3 \times 4 \bmod 5 = 2 解释： 2=\frac{8}{4} \bmod 5$$
• $$a=2,b=4,m=6时 \\ \because \text{gcd}(b,m)\neq 1\\ \therefore a=2,b=4,m=6 \Longleftrightarrow a=1,b=2,m=3 \\ \therefore 模m下b^{-1}=2\\ \therefore \frac{A}{B} \bmod m = a \times b^{-1} \bmod m= 1 \times 2 \bmod 3 = 2,5 解释： 2=\frac{8}{4} \bmod 6,5=\frac{20}{4} \bmod 6$$

线性求逆元

如果要求$1$到$n-1$的逆元，如果用扩展欧几里得定理或者其他的算法一个一个算时间复杂度为$O(n \log n)$，太慢。

不妨考虑以下算法：

$$对于1到n-1的一个数i, 设r=n \bmod i,将p用余数表示法表示为n=\lfloor \frac{n}{i} \rfloor\times i+r\\ 于是:\\ \lfloor \frac{n}{i} \rfloor \times i + r \equiv 0 \pmod n\\ \lfloor \frac{n}{i} \rfloor \times i \times (i^{-1}\times r^{-1}) + r \times (i^{-1}\times r^{-1}) \equiv 0 \pmod n\\ \lfloor \frac{n}{i} \rfloor \times r^{-1} +i^{-1} \equiv 0 \pmod n\\ i^{-1} \equiv - \lfloor \frac{n}{i} \rfloor \times r^{-1} \pmod n\\ 又\because 1^{-1} \equiv 1 \pmod p\\ \therefore i^{-1} = \begin{cases}当i=1时 & 1 \\当i\neq 1时 & (-\lfloor \frac{n}{i}\rfloor \times r^{-1}) \bmod n \end{cases}\\ \because r= n \bmod i\\ \therefore r<i\\ \therefore 只需要从1到n-1顺序遍历一遍，当遍历到i时，r一定算出来了，所以可以O(1)求出模n下的i^{-1}\\ \therefore 该算法的时间复杂度为O(n)$$

线性求逆元的代码

vector<int> inv(n + 1, 1);
for (int i = 2; i <= n; i++) inv[i] = mod(-n / i * inv[n % i], n);

阶乘求逆元

求$0到n$阶乘模p的逆元

显然，$\frac{1}{n!}\times n = \frac{1}{n-1}$

$\therefore (n-1)^{-1} \equiv n^{-1} \times n \pmod p$

只需要先求出n的逆元，在从n到1遍历求逆元即可，时间复杂度为$O(n)$

阶乘求逆元的代码

vector<int> inv(n + 1);
inv[n] = inv(n, p);
for (int i = n; i >= 1; i--) inv[n - 1] = (inv[n] * i) % p;

---

中国剩余定理（孙子定理）

定义

对于形如$\begin{cases}x\equiv a_1\pmod {m_1}\\x\equiv a_2 \pmod {m_2}\\\dots\\x\equiv{a_n}\pmod {m_n}\end{cases}$的方程组，称为线性同余方程组，而中国剩余定理 (Chinese Remainder Theorem) 算法可以求解

具体的，当$\text{gcd}(m_1,m_2)=\text{gcd}(m_2,m_3)=\cdots=\text{gcd}(m_{n-1},m_n)=1$时该方程组有解。

核心思想

不妨令$M=\Pi _{i=1} ^{n} m_i$,$M_i=\frac{M}{m_i}$ 。我们发现$kM_i$当$j\neq i$时，$kM_i\equiv 0 \pmod {m_j}$，接下来令$kM_i\equiv a_i \pmod {m_i}$,就可以达到$kM_i$对于第$i$条是正确的，并且对于不是第$i$条的方程不影响。我们不妨将$1至n$的所有$kM_i$求解并求和，就可以得到一个解，再将其取模$M$,就是答案的最小正值。

举例：

$$\begin{array}{c} \left\{\begin{matrix} x \equiv 2 \pmod 3\\ x \equiv 3 \pmod 5\\ x \equiv 2 \pmod 7\\ \end{matrix}\right.\\ 35k\equiv2 \pmod 3\\ 解得k=1\\ 21k\equiv3 \pmod 5\\ 解得k=3\\ 15k\equiv2 \pmod 7\\ 解得k=2\\ x_1=35\times 1+21 \times 3 + 15 \times 2=128\\ x=128 \bmod (3\times 5 \times 7)=23 \end{array}$$

因为$m$两两互质，所以不用担心$kM_i\equiv a_i \pmod {m_i}$这些方程无解

小结

是否存在21个连续的正整数，使得其中每个数均被至少一个$2 \sim 13$ 的素数整除？若有，请写出这21个正整数的中间数的最小值；若没有，请说明理由。

$$\begin{array}{c} 解：\\ 不妨设中间数为x\\ 假如x能被某些2到13的质数整除:p_1,p_2\cdots p_n\\ 那么对于1\leqslant i \leqslant n, p_i\mid(x\pm k\times p_i)\\ 我们只需关注x\pm 10 之内的数，也就是说x不必整除11,13\\ 那便假设2\times 3\times 5\times 7 \mid x\\ 则：\\ \begin{matrix} 数字： x-10 & x-9 & x-8 & x-7 & x-6 & x-5 & x-4 & x-3 & x-2 & x-1 & x & x+1 & x+2 & x+3 & x+4 & x+5 & x+6 & x+7 & x+8 & x+9 & x+10 \\ 能整除的质数： 2,5 & 3 & 2 & 7 & 2,3 & 5 & 2 & 3 & 2 & ? & 2,3,5,7 & ? & 2 & 3 & 2 & 5 & 2,3 & 7 & 2 & 3 & 2,5 \\ \end{matrix}\\ 我们这样做的好处是现在只有x-1,x+1没有整除一个素数，怎么办呢？\\ 显然，2,3,5,7\nmid x-1,x+1，那就让11,13分别整除x-1,x+1\\ 情况一：11\mid x-1 ,13 \mid x+1\\ \because 2 \times 3 \times 5 \times 7 \mid x,(x-1) \mid 11,(x+1)\mid 13\\ \therefore x-1 \equiv 0 \pmod {11},x+1 \equiv 0 \pmod {13}\\ \therefore 可以列出方程组： \left\{\begin{matrix} x \equiv 1 \pmod {11}\\ x \equiv 12 \pmod {13}\\ x \equiv 0 \pmod {210} \end{matrix}\right.\\ 可以根据中国剩余定理求解，解得x=9450+30030k\\ 答：x=9450 \end{array}\\$$

代码实现

pair<long long, bool> SolveCongruenceEquation(long long a, long long b, long long mod);  // 求解ax ≡ b (mod)
long long ChineseRemainderTheorem(vector<long long>& rmdi, vector<long long>& modi) {
  long long factor = 1, result = 0;
  for (long long x : modi) factor *= x;
  for (int i = 0; i < rmdi.size(); i++) result += factor / modi[i] * SolveCongruenceEquation(factor / modi[i], rmdi[i], modi[i]).first;
  return result % factor;
}

欧拉函数及定理

定义

$\phi(x)$：欧拉函数，即$1\sim x$中与$x$互质的数的个数

特别的，$\phi (1)=1$

性质

1. $\phi(1)=1$
2. $\phi(p)=p-1$（p为质数）
3. $\phi(p^b)=p^b-p^{b-1}$(p为质数)
4. 欧拉函数是积性函数，即若a,b互质，$\phi(a\times b)=\phi(a)\times \phi(b)$
5. $\phi(x)=x\times \Pi _{i=1} ^n (1-\frac{1}{p_i})$(n为x分解质因数后的质数个数)
6. 欧拉定理：当a与x互质时，$a^{\phi(x)}\equiv 1 \pmod x$

性质的证明

性质3的证明：

$$回归定义，\phi(p^b)是1\sim p^b中与p^b互质的数的个数\\ 即\phi(p^b)=p^b-(1\sim p^b中与p^b不互质的数的个数)\\ 那么1\sim p^b中与p^b不互质的数到底有多少呢？\\ 因为p为质数，所以不互质p^b的数一定是p的倍数：1p,2p,3p,\cdots p^{b-1}\times p，一共有p^{b-1}个\\ \therefore \phi(p^b)=p^b-p^{b-1}\\$$

性质4的证明

还是刚才的那个思想，$\phi(a\times b)=1 到 ab$中与$ab$互质的数的个数
我们列出$1 \sim ab$的所有整数：

原数	原数模$a$的结果	原数模$b$的结果
1	$1 \bmod a$	$1 \bmod b$
2	$2 \bmod a$	$2 \bmod b$
⋮	⋮	⋮
$ab$	$0$	$0$

将右两列组成数对：$(x \bmod a, x \bmod b)$
因为$\gcd(a,b)=1$，有：
$\gcd(x, ab) = 1 \iff \gcd(x, a) = 1 \ \text{且}\ \gcd(x, b) = 1 \iff \gcd(x \bmod a, a) = 1\ \text{且}\ \gcd(x \bmod b, b) = 1$

所以，当且仅当$x$同时满足以下两个条件时，$x$与$ab$互质：

$\begin{cases} \gcd(x \bmod a, a) = 1 \\ \gcd(x \bmod b, b) = 1 \end{cases}$

因为$a$和$b$互质，所有数对$(x \bmod a, x \bmod b)$互不相同（即不同$x$对应不同数对），因此原数$x$与数对$(u,v)$一一对应。

观察数对中的分量：

• 模$a$的余数取值范围是$0 \sim (a-1)$，其中与$a$互质的数有$\phi(a)$个
• 模$b$的余数取值范围是$0 \sim (b-1)$，其中与$b$互质的数有$\phi(b)$个

要同时满足两个互质条件，数对的选择数量为：
$\phi(a \times b) = \phi(a) \times \phi(b)$

---

举例： $a=3, b=5$，则$ab=15$

原数	模3余数	模5余数	与15互质条件
1	1	1	是
2	2	2	是
3	0	3	否
4	1	4	是
5	2	0	否
6	0	1	否
7	1	2	是
8	2	3	是
9	0	4	否
10	1	0	否
11	2	1	是
12	0	2	否
13	1	3	是
14	2	4	是
15	0	0	否

表中加粗表示满足与该模数互质：

• 模3余数中与3互质的有2个：{1,2} ($\phi(3)=2$)
• 模5余数中与5互质的有4个：{1,2,3,4} ($\phi(5)=4$)
  同时满足两个条件的数有8个，即$\phi(15)=8=\phi(3)\times\phi(5)$

性质5的证明

$$想要求x的值，不妨将它质因数分解,假设x=\Pi _{i=1}^n p_i^{a_i}\\ \phi(x)=\phi(\Pi _{i=1}^n p_i^{a_i})\\ \because 欧拉函数是积性函数\\ \therefore \phi(x)=\Pi _{i=1} ^n \phi(p_i^{a_i})\\ 又\because p_i为质数\\ \therefore \phi(x)=\Pi _{i=1} ^n (p_i^{a_i}-p_i^{a_i-1})=\Pi _{i=1} ^n p_i^{a_i}(1-\frac{1}{p_i})=\Pi _{i=1} ^n p_i^{a_i} \times \Pi_{i=1}^n (1-\frac{1}{p_i})=x \Pi_{i=1} ^n (1-\frac{1}{p_i})\\ 证毕\\ ----------\\ 举例：\\ 计算\phi(1000)\\ 1000=2^3\times 5^3\\ \phi(1000)=1000\times (1-\frac{1}{2})\times (1-\frac{1}{5})=1000\times \frac{1}{2}\times \frac{4}{5}=400$$

欧拉定理的证明

$$假设 a 与 x 互质，且 0 \leqslant a < x。考虑 1 至 x 中与 x 互质的所有整数，记为 b_1, b_2, \dots, b_{\phi(x)}。定义c_i = b_i \times a 和 d_i = c_i \bmod x。\\ 序列 b 满足： \\ \begin{cases} 当 i \neq j 时, \ b_i \neq b_j, \\ \text{gcd}(b_i, x) = 1. \end{cases}\\ 分析 d_i 的性质：\\ 问题：d_i = d_j 是否可能成立（对于 i \neq j）？ \\ 反证法： 假设 d_i = d_j（其中 i \neq j）。 \\ 则 c_i \equiv c_j \pmod{x}，即 (b_i \times a \equiv b_j \times a \pmod{x})。 \\ 由同余性质，得 a(b_i - b_j) \equiv 0 \pmod{x}。 \\ 由于 \text{gcd}(a, x) = 1，因此 b_i - b_j \equiv 0 \pmod{x}。 \\ 又因 1 \leqslant b_i, b_j \leqslant x，故 b_i = b_j，与条件 i \neq j 矛盾。 因此，d_i \neq d_j，即 d 满足互异性。\\ 互质性：\text{gcd}(d_i, x) = \text{gcd}(c_i \bmod x, x) = \text{gcd}(c_i, x) = \text{gcd}(a \times b_i, x)。 \\ 由于 \text{gcd}(a, x) = 1 且 \text{gcd}(b_i, x) = 1，有 \text{gcd}(a \times b_i, x) = 1。\\ 因此，\text{gcd}(d_i, x) = 1，即 d 满足互质性。\\ 综上，序列 d 与 b 除了顺序可能不同，其他均相同。\\ ---------------\\ 示例：\\ 设 x = 5，则与 5 互质的数为 b = 1, 2, 3, 4（即 \phi(5) = 4）。 \\ 取 a = 3，有 c_i = b_i \times 3 = [3, 6, 9, 12]。 \\ 计算 d_i = c_i \bmod 5 = [3, 1, 4, 2]，与 b 相同但顺序不同。\\ ---------------\\ 欧拉定理的推导： \\ 由于 d 是 b 的重新排列，其乘积满足: \\ b_1 b_2 \cdots b_{\phi(x)} \equiv d_1 d_2 \cdots d_{\phi(x)} \pmod{x}.\\ 又因 d_i \equiv a b_i \pmod{x}，故: \\ d_1 d_2 \cdots d_{\phi(x)} \equiv (a b_1)(a b_2)\cdots[a b_{\phi(x)}] \pmod{x}.\\ 因此， \\ b_1 b_2 \cdots b_{\phi(x)} \equiv a^{\phi(x)} [b_1 b_2 \cdots b_{\phi(x)}] \pmod{x}.\\ 整理得: \\ [a^{\phi(x)} - 1] b_1 b_2 \cdots b_{\phi(x)} \equiv 0 \pmod{x}.\\ 由于每个 b_i 与 x 互质，其乘积 b_1 b_2 \cdots b_{\phi(x)} 也与 x 互质（因数均互质）。 \\ 故a^{\phi(x)} - 1 \equiv 0 \pmod{x}, \\ \therefore a^{\phi(x)} \equiv 1 \pmod{x}.\\ 证毕$$

欧拉定理

当$\text{gcd}(a,n)=1时，a^b\equiv a^{b \bmod \phi(n)} \pmod n$

证明:

$$设r=b \bmod \phi(n),k=\frac{b-r}{\phi(n)}\\ \therefore a^b \equiv a^{k\phi(x)+r}\equiv [a^{\phi(x)}]^{k}\times a^r \equiv 1^k \times a^r \equiv a^r \equiv a ^{b \bmod \phi(n)} \pmod n\\$$

小结

1. 计算$7^{105} \bmod 10$

   $$\because \text{gcd}(7,100)=1\\ \therefore 7^{\phi(10)}\equiv 7^4\equiv1 \bmod 10\\ \therefore 7^{105}\equiv7^{100 +1} \equiv {(7^4)}^{26} \times 7^1 \equiv 7 \pmod {10}\\ 答：7\\ 我们发现欧拉定理的有降幂的作用，也就是欧拉定理的推论：\text{gcd}(a,n)=1时，a^b\equiv a^{b \bmod \phi(n)} \pmod n\\ 你可能会问，若\text{gcd}(a,n)=1时能不能降幂呢？\\ 后文会讲到「扩展欧拉定理」\\ 再补充一句，b \bmod \phi(n)是欧拉定理做到降幂的极限，不是最小的值！！！$$

2. $1032^{1032}$的最后两位？

   $$其实就是要我们求1032^{1032}\equiv ? \pmod {100}\\ 首先，1032^{1032}\equiv 32^{1032} \pmod {100}\\ 设x\equiv 32^{1032} \pmod {100},则:\\ x\equiv 0 \pmod 4\\ x\equiv 32^{1032 \bmod \phi(25)}\equiv 32^{12}\equiv 7^{12} \equiv 49^6 \equiv (-1)^6 \equiv 1 \pmod {25}\\ \\ 有方程组:\begin{cases} x \equiv 0 \pmod 4 \\ x \equiv 1 \pmod {25} \end{cases}\\ 根据中国剩余定理，解得x\equiv 76 \pmod {100}\\ \therefore 1032^{1032}\equiv 76 \pmod {100}\\ 通过这个例题，我们学会了当底数与模数不互质时，可以用中国剩余定理求解，这就是为什么要把这一章放在中国剩余定理之后的原因。\\ 更具体的,令x=a^b \bmod m，将模数m质因数分解p_1^{e_1}\times p_2^{e_2}\times \cdots p_n^{e_n},\\ 先用欧拉定理求解a^{b}\equiv x \pmod {p_1^{e_1}},再用中国剩余定理把互质的模数拼起来,就能求解出答案了(因为当i\neq j时，\text{gcd}(p_i^{e_i},p_j^{e_i})=1)\\$$

3. 定义$\begin{cases}f(1)=1 \\当n为正整数时\quad f(n)=n^{f(n-1)} \end{cases}$,求$f(2008)$的最后3位。

   $$求2008^{2007^{2006^\cdots}} \bmod 1000 （注：这是2008^{(2007^{(2006^\cdots)})} \bmod 1000的简化记法）\\ 因为\text{gcd}(2008,1000)\neq 1\\ \therefore 先求出2008^{2007^{2006^\cdots}} \bmod 8和2008^{2007^{2006^\cdots}} \bmod 125，再用中国剩余定理拼起来。\\ 设x=2008^{2007^{2006^\cdots}} \bmod 1000\\ 2008^{2007^{2006^\cdots}} \equiv (2\times 1004)^{2007^{2006^\cdots}} \equiv 2^{2007^{2006^\cdots}} \times 1004^{2007^{2006^\cdots}} \equiv 0 \pmod 8 \quad ...[1]\\ 2008^{2007^{2006^\cdots}}\equiv 2008^{[2007^{2006^\cdots} \bmod \phi(125)]} \equiv 2008^{[2007^{2006^\cdots} \bmod 100]} \equiv 2008^{[7^{2006^\cdots} \bmod 100]} \pmod {125} \\ 接下来求出7^{2006^{2005\cdots}} \bmod 100即可\\ \because \text{gcd}(7,100)=1\\ 接下来观察7的幂次最后两位的规律：\\ 7^0 \equiv 1 \pmod {100} \\ 7^1 \equiv 7 \pmod {100} \\ 7^2 \equiv 49 \pmod {100} \\ 7^3 \equiv 43 \pmod {100} \\ 计算2006^{2005^{2004^\cdots}} \bmod 4\\ 显然，它=0\\ \therefore 7^{2006^{2005^\cdots}} \bmod 100=1\\ \therefore x \equiv 2008^{[7^{2006^\cdots} \bmod 100]} \equiv 2008^1 \equiv 8 \pmod {125} \quad ...[2]\\ \begin{cases} x\equiv 0 \pmod 8\\ x\equiv 8 \pmod {125} \end{cases}\\ 解得x\equiv 8 \pmod {1000}\\ 答：008$$

4. 求证当 $n \geqslant 3$ 时，$n^{n^n} \equiv n^n \pmod{16}$

   证明： 分两种情况讨论：

   1. $n$为偶数：

      $$\because n\geqslant 3 且 2\mid n\\ \therefore n\geqslant 4\\ 又\because n\geqslant 2,n^n\geqslant 2\\\ \therefore n^{(n^n)}\equiv n^n \equiv 0 \pmod {16}$$

   2. $n$为奇数：

      $$不妨先证明当n为奇数时，n^4 \equiv 1 \pmod {16}\\ 设n=2k+1\\ \because (2k+1)^4=16k^4+32k^3+24k^2+8k+1\\ \therefore n^4 \equiv 16k^4+32k^3+24k^2+8k+1 \equiv 8k^2+8k+1 \equiv 16\times \frac{(k+1)\times k}{2}+1 \equiv 1 \pmod {16} （因为\frac{(k+1)k}{2}=C_{k+1}^2是整数）\\ \because 2\nmid n,n^4\equiv 1\pmod {16}\\ \therefore n^{(n^n)}\equiv n^n \pmod {16}\Longleftrightarrow n^n \equiv n \pmod 4 \Longleftrightarrow n\equiv 1 \pmod 2 \Longleftrightarrow 1\equiv 0 \pmod 1\\ 证毕$$

   你可能会发现，欧拉函数的降幂并不一定是最优的，就像这个例子：当$n\geqslant 3$时$n^4\equiv 1 \pmod {16}$

5. 求证当 $n \geq 3$ 时，$1989 \mid n^{n^{n^n}} - n^{n^n}$

   证明： 由 $1989 = 9 \times 13 \times 17$，只需证模 $9,13,17$ 成立：

   1. 模 $9$：
      • 若 $3 \mid n$，则 $n^n$ 和 $n^{n^n}$ 均被 $9$ 整除（∵ $n \geq 3$)。
      • 若 $3 \nmid n$，则需 $n^n \equiv n^{n^n} \pmod{6}$。 ∵ 模 $2$ 和模 $3$ 均同余（奇偶性一致且 $n \equiv \pm 1 \pmod{3}$)， ∴ 成立。
   2. 模 $13$：
      • 若 $13 \mid n$，则两边模 $13$ 为 $0$。
      • 若 $13 \nmid n$，则需 $n^n \equiv n^{n^n} \pmod{12}$。 ∵ 模 $4$（偶数整除/奇数同余）和模 $3$ 均同余， ∴ 成立。
   3. 模 $17$：
      • 若 $17 \mid n$，则两边模 $17$ 为 $0$。
      • 若 $17 \nmid n$，则需 $n^n \equiv n^{n^n} \pmod{16}$， 由问题4结论成立。

   综上，原式被 $1989$ 整除。

   具体证明就留作课后作业吧$\sim$

欧拉定理求逆元，费马小定理，扩展欧拉定理

欧拉定理求逆元

根据欧拉定理，当$\text{gcd}(a,n)时，$ $a^{\phi(n)}\equiv 1 \pmod n$

$\therefore a\times a^{\phi(n)-1}\equiv 1 \pmod n$

$\therefore a^{\phi(n)-1}+k\times n$是$a$模$n$的逆元

费马小定理

当$n$为质数且$n \nmid a$时，$a^{n-1}\equiv 1 \pmod n$

证明（有多种证明方法，这里给出一种最简单的）:

$$\because n\nmid a , n是质数\\ \therefore \text{gcd}(a,n)=1\\ 根据欧拉定理,\therefore a^{\phi(n)}\equiv 1 \pmod n \\ \because n为质数\\ \therefore \phi(n)=n-1\\ \therefore a^{n-1}\equiv 1 \pmod n\\ 证毕$$

费马小定理求逆元

根据费马小定理,当$n$为质数时，

$根据费马小定理，有a^{n-1} \equiv 1 \pmod n$

$\therefore a\times a^{n-2} \equiv 1 \pmod n$

$\therefore (a^{n-2}+kn)是a模n的逆元$

扩展欧拉定理

定理

$\forall a,b,c \in \mathbb{N^+},满足 a^b \equiv \begin{cases} a^b & b \lt \phi(c)\\ a^{b\bmod \phi(c)+\phi(c)} & b \geqslant \phi(c) \end{cases} \pmod c$

第一行表示$a^b \bmod c$当$b \lt \phi(c)$时无法用欧拉定理降幂。

定理的证明

接下来我们证明第二行$a^b \equiv a^{b \bmod \phi(c) +\phi(c)} \pmod c$

• 先证明两个引理：

  1. 对于如果$p,q$互质，且同时满足$x\equiv y \pmod p ,x\equiv y \pmod q$ 那么有$x\equiv y \pmod {pq}$

     $$根据同余的性质，有(x-y) = k_1 p,(x-y) = k_2 q\\ 其中k_1,k_2都是整数\\ \because (x-y)是p的倍数,也是q的倍数\\ \therefore (x-y)至少是p，q的最小公倍数的倍数\\ \therefore \text{lcm}(p,q) \mid (x-y)\\ 又\because p,q互质\\ \therefore pq\mid (x-y)\\ \therefore x\equiv y \pmod {pq}$$

  2. 对于素数的整数次幂$p^e$,有$\phi(p^e)\geqslant e$

     $$只需证明极端情况：p最小时成立即可，即p=2\\ 即证2^{e-1}\geqslant e\\ 注意到，当e=1时显然成立\\ 假设不等式在k处成立,需证它在(k+1)处也成立 \quad (k大于等于1)\\ \because 2^{k-1} \geqslant k\\ \therefore 2^k \geqslant 2k\\ 又\because k \geqslant 1\\ \therefore 2k \geqslant k+1\\ \therefore 2^k \geqslant 2k \geqslant k+1\\ \therefore 证毕$$

• 将$c$质因数分解,设$c=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$

​ 根据同余性质，若p,q互质，且$x\equiv y \pmod p$,$x\equiv y \pmod q$，那么$x\equiv y \pmod {pq}$

​ 根据引理1，只需证明对于每个$p_i^{e_i}$，满足$a^b \equiv a^{b\bmod \phi(c)+\phi(c)} \pmod {p_i^{e_i}}$

1. $\text{gcd}(a,p_i^{e_i})=1$时

   $$根据欧拉定理\\ a^{\phi(p_i^{e_i})}\equiv 1 \pmod {p_i^{e_i}}\\ 因为欧拉函数是积性函数\\ \therefore a^{\phi(c)}\equiv a^{\phi(p_i^{e_i})\times k} \equiv 1 \pmod {p_i^{e_i}}\\ 根据余数表示法，有b=\lfloor \frac{b}{\phi(c)} \rfloor \times \phi(c) + b \bmod \phi(c)\\ \therefore a^b \equiv a^{\lfloor \frac{b}{\phi(c)} \rfloor \times \phi(c) + b\bmod \phi(c)} \equiv a^{\lfloor \frac{b}{\phi(c)} \rfloor \phi(c)} \times a^{b\bmod \phi(c)}\equiv 1\times a^{b \bmod \phi(c)}\equiv a^{b \bmod \phi(c)}\times a^{\phi(c)}\equiv a^{b \bmod \phi(c) +\phi(c)} \pmod {p_i^{e_i}}$$

2. $\text{gcd}(a,p_i^{e_i}) \neq 1$时

   $$\because p_i为质数,\text{gcd}(a,p_i^{e_i})\\ \therefore p_i \mid a\\ \therefore 设a=np_i\\ \because b\geqslant \phi(c),\phi(p_i^{e_i})\geqslant e_i,欧拉函数是积性函数\\ \therefore 有如下连等式 b \geqslant \phi(c) \geqslant \phi(p_i^{e_i}) \geqslant e_i\\ \because a=np_i\\ \therefore a^b = {(np_i)}^b = n^b \times p_i^{b-e_i}\times p_i^{e_i}\\ \because b\geqslant e_i\\ \therefore p_i^{e_i} \mid a^b,a^b \equiv 0 \pmod {p_i^{e_i}}\\ 同理，a^{b\bmod \phi(c)+\phi(c)}={(np_i)}^{b\bmod \phi(c)+\phi(c)}=n^{b\bmod \phi(c)+\phi(c)}\times p_i^{b\bmod \phi(c)+\phi(c)-e_i}\times p_i^{e_i}\\ \therefore p_i^{e_i} \mid a^{b\bmod \phi(c) +\phi(c)},a^{b \bmod \phi(c)+\phi(c)}\equiv 0 \pmod {p_i^{e_i}}\\ \therefore a^b \equiv a^{b\bmod \phi(c)+\phi(c)} \equiv 0 \pmod {p_i^{e_i}}$$

意义

不需要考虑$a,c$互不互质了。

在我们只会欧拉定理时，当$a,c$不互质时，使用的方法是拆模数。

现在会了扩展欧拉定理，就多了一种方法，但不代表前一种方法没用了，因为扩展欧拉定理降幂的模数很难达到最优

小结

第12题没什么好讲的（远没有扩展欧拉定理难证），就留作课后作业了

---

如有错误欢迎指出，转载请标明出处@renhongxuuu