初等数论笔记

一元多项式环理论中有许多概念和数论相通，尤其是整除关系、辗转相除法、不可约多项式部分。通过考察对比，可以对环的概念认知更加深刻，同时引出环同态、欧几里得整环等概念。而且数论是基础性的知识，在高中数学竞赛和信息竞赛都有涉及，值得恶补一番！

整除

定义

任给两个整数 $a,b$，其中 $b \neq 0$，如果存在一个整数 $q$ 使得等式

$$a=bq$$

成立，则称 $b$ 整除 $a$，记作 $b\mid a$，并称 $b$ 是 $a$ 的因数， $a$ 是 $b$ 的倍数。

值得一提的是，整除在 $\LaTeX$ 中应当以 \mid 指令来输入^[1]，而不是直接输入单竖线 | 。区别在于 \mid 能提供合适间隙。同样，不整除符号 $\nmid$ 应当用 \nmid 指令输入。

性质

• 传递性：若 $b \mid a$，且 $c \mid a$，则 $b\mid a$ 。

• 加减封闭：若 $b \mid a$，且 $b \mid c$，则 $b \mid (a \pm c)$ ；更进一步地，$b \mid (au+cv)$，其中 $u,v$ 为任意整数。

• 有序性：若 $b \mid a$，则或者 $a=0$，或者 $|b| \le |a|$；这意味着，若 $b \mid a$ 且 $a \mid b$ ，则 $|a|=|b|$。

• 成对因子：若 $b \mid a$ 且 $a \neq 0$，则 $\frac{a}{b} \mid a$ 。

• 带余除法：设 $a,b$ 为整数，$b>0$，则存在唯一的整数 $q$ 和 $r$，使得

  $$a=bq+r,\,0\le r < b$$

  $q$ 叫做 $a$ 被 $b$ 除得的不完全商，$r$ 称为余数。

例题

1. 对于十进制正整数 $n$，求证：它能够被 $9$ 整除的充要条件是各数位上的数字之和为 $9$ 的倍数^[2]。

   Proof

   设 $n$ 各数位上的数字之和为 $S(n)$，设 $n=a_k \times 10^k + \cdots + a_1 \times 10 + a_0$，其中 $0\le a_o \le 9,a_k \neq 0$。

   则 $S(n)=a_0+a_1+\cdots+a_k$。于是有

   $$n-S(n)=a_k(10^k -1)+\cdots +a_1 (10 -1)$$

   显然 $9 \mid n-S(n)$ 。由性质2，便有 $9 \mid n \iff 9 \mid S(n)$ 。

   /* 利用性质2考虑和差是常见的证明整除的方法 */

最大公因数

定义

设 $a_1,a_2,\cdots,a_n$ 是 $n$ 个不全为 $0$ 的整数。若整数 $d$ 是它们之中每一个的因数，则 $d$ 就叫做 $a_1,a_2,\cdots,a_n$ 的一个公因数。由性质 $3$，公因数只有有限多个。取其中最大的一个称为 $a_1,a_2,\cdots,a_n$ 的最大公因数，记作 $\gcd (a_1,a_2,\cdots,a_n)$。在不引起混淆的情况下，简记为 $(a_1,a_2,\cdots,a_n)$。特殊地，若 $(a_1,a_2,\cdots,a_n)=1$，则称 $a_1,a_2,\cdots,a_n$ 互素。^[3]

最大公因数的英文是 Greatest Common Divisor，这就是缩写为 $\gcd$ 的原因。

辗转相除法

设 $a,b$ 是不全为 $0$ 的整数，且 $a=bq+r$，则 $(a,b)=(b,r)$ 。

Proof

由 $(a,b) \mid a$，且 $(a,b) \mid b$，于是 $(a,b) \mid r$，即 $(a,b)$ 是 $b,r$ 的公因数，由最大公因数的定义 $(a,b) \le (b,r)$ 。同理， $(b,r) \le (a,b)$ 。因此 $(b,r) = (a,b)$ 。

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

辗转相除法是深刻的性质，能作辗转相除法的整环称为欧几里得整环。

裴蜀定理

定理

设 $a,b$ 是不全为零的整数，则存在整数 $x,y$，使得 $ax+by=(a,b)$ 。

构造性证明

利用辗转相除法^[4]

若 $a,b$ 任何一个等于 $0$，不妨设 $b=0$，则 $(a,b)=a$ 。这时定理显然成立。

若 $a,b \neq 0$，由于 $(a,b)=(a,-b)$，不妨设 $a>b \ge 0$ 。

要证存在整数 $x,y$ 使得 $ax+by=(a,b)$，即证 $\dfrac{a}{(a,b)}x+\dfrac{b}{(a,b)}y=1$ 。

令 $a_1=\dfrac{a}{(a,b)},b_1=\dfrac{b}{(a,b)}$，即证满足该关系的两个数 $a_1,b_1$，总存在整数 $x,y$，使得 $a_1 x+b_1 y=1$ 。

引理：已知 $a,b$ 为正整数，则 $\gcd\left(\dfrac{a}{(a,b)},\dfrac{b}{(a,b)}\right)=1$ 。

引理的证明：利用反证法。假设 $\exist d>1$，使得 $d \:\: \biggm| \dfrac{a}{(a,b)}$ 且 $d \:\: \biggm| \dfrac{a}{(a,b)}$，则有 $d(a,b) \mid a$ 且 $d(a,b) \mid b$ 。而 $d(a,b)>(a,b)$，这意味着 $d(a,b)$ 成为了新的最大公因数，与 $(a,b)$ 的定义矛盾。故 $d=1$，即它们互素。

于是根据引理，我们得知 $a_1,b_1$ 互素。

下面考虑辗转相除法的运算过程，其计算 $a_1,b_1$ 最大公因数最后得到的结果应当为 $1$，即

$$\gcd\left(a_{1}, b_{1}\right)=\gcd\left(b_{1}, r_{1}\right)=\gcd\left(r_{1}, r_{2}\right)=\cdots=\gcd\left(r_{n-1}, r_{n}\right)=\gcd(r_n,r_{n+1})=1$$

根据上面的代码，循环在 $r_{n+1}=0$ 时退出，此时 $r_n=1$ 。写出带余除法递推式：

$$\begin{aligned} a_{1}&=q_{1} b_1+r_{1} \\ b_{1}&=q_{2} r_{1}+r_{2} \\ r_{1}&=q_{3} r_{2}+r_{3} \\ &\cdots\\ r_{n-3}&=q_{n-1} r_{n-2}+r_{n-1} \\ r_{n-2}&=q_{n} r_{n-1}+r_{n} \\ r_{n-1}&=q_{n+1}r_{n} \end{aligned}$$

写成矩阵形式

$$\begin{bmatrix} a_1 \\ b_1 \end{bmatrix} = \begin{bmatrix} q_1 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} b_1 \\ r_1 \end{bmatrix}$$

$$\begin{bmatrix} b_1 \\ r_1 \end{bmatrix} = \begin{bmatrix} q_2 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} r_1 \\ r_2 \end{bmatrix}$$

$$\begin{bmatrix} r_1 \\ r_2 \end{bmatrix} = \begin{bmatrix} q_3 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} r_2 \\ r_3 \end{bmatrix}$$

$$\vdots$$

$$\begin{bmatrix} r_{n-2} \\ r_{n-1} \end{bmatrix} = \begin{bmatrix} q_n & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} r_{n-1} \\ r_{n} \end{bmatrix}$$

$$\begin{bmatrix} r_{n-1} \\ r_{n} \end{bmatrix} = \begin{bmatrix} q_{n+1} & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} r_{n} \\ r_{n+1} \end{bmatrix} = \begin{bmatrix} q_{n+1} & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} 1 \\ 0 \end{bmatrix}$$

将下一个矩阵形式代入上一个，得到

$$\begin{bmatrix} a_1 \\ b_1 \end{bmatrix} = M \begin{bmatrix} 1 \\ 0 \end{bmatrix}$$

其中

$$M=\begin{bmatrix} q_1 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} q_2 & 1\\ 1 & 0 \end{bmatrix} \cdots\begin{bmatrix} q_{n+1} & 1\\ 1 & 0 \end{bmatrix}$$

并且 $\det M = (-1)^{n+1}$。设

$$M=\begin{bmatrix}\lambda & \mu \\ \tau & \sigma\end{bmatrix}$$

由于 $q_i$ 是整数，由矩阵乘法，$\lambda,\tau,\mu,\sigma$ 也为整数。进而得到

$$\begin{bmatrix} a_1 \\ b_1 \end{bmatrix} = \begin{bmatrix}\lambda & \mu \\ \tau & \sigma\end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} \lambda \\ \tau \end{bmatrix}$$

因此 $\lambda =a_1, \tau=b_1$，即

$$M=\begin{bmatrix}a_1 & \mu \\ b_1 & \sigma \end{bmatrix}$$

由于 $\det M = (-1)^{n+1}$，因此可得

$$a_1 \sigma - b_1 \mu =(-1)^{n+1}$$

这样一来，对于要解的不定方程 $a_1 x+b_1 y=1$，取 $x=\sigma,y=-\mu$ 或 $x=-\sigma,y=\mu$ 中的一组即为不定方程的解。

非构造性证明

参看维基百科

推论

1. 对于 $\forall x,y \in \Z$，$f(x,y)=ax+by$ 的最小正整数取值为 $(a,b)$。
2. 设 $a,b$ 是给定的不全为 $0$ 的整数，则不定方程/线性丢番图方程 $ax+by=m$，有整数解的充分必要条件是 $(a,b) \mid m$ 。
3. 两个整数 $a,b$ 互素的充分必要条件是存在整数 $x,y$，使得 $ax+by=1$ 。
4. 存在无穷多组 $(x,y)$，使得 $ax+by=(a,b)$ 。并且当 $ab>0$ 时，$x,y$ 异号。

性质

• 若 $m \mid a, \, m \mid b$，则 $m \mid (a,b)$，即 $a,b$ 的任何一个公因数都是其最大公因数的因数；

• 若 $(a,m)=1,\, (b,m)=1$，则 $(ab,m)=1$，即与一个固定整数互素的整数之集关于乘法封闭；

  进而，若 $(a,b)=1$，则 $\forall k,l>0$，都有 $(a^k,b^l)>0$ 。

• 设 $b \mid ac$，若 $(b,c)=1$，则 $b \mid a$ 。

• 设 $a,b$ 互素，且 $ab=m^k\,(k \ge 2)$，则 $a,b$ 都是一个整数的 $k$ 次幂；

  一般地，若 $a_1, a_2, \cdots, a_n$ 互素，且 $a_1 a_2 \cdots a_n = m^k$，则 $a_1, a_2, \cdots, a_n$ 都是一个整数的 $k$ 次幂。

例题

1. $\forall n \in \Z,$ 求证：$\dfrac{12n+5}{9n+4}$ 是既约分数。

   Proof

   由于 $4(9n+4)-3(12n+5)=1$，所以 $12n+5$ 和 $9n+4$ 互素。

   /* ax+by=1 判断互素是锐利的性质 */

2. 设 $n$ 是正整数，求证：$(n!+1,(n+1)!+1)=1$ 。

   Proof

   由于 $(n!+1)(n+1)-[(n+1)!+1]=n$，所以 $\gcd(n!+1,(n+1)!+1) \mid n$ 。

   不妨设 $(n!+1,(n+1)!+1)=d$，则 $d \mid n$，进而得到 $d \mid n!$ 。

   又因为 $d \mid (n!+1)$，所以 $d=1$ 。

3. 设 $b \mid ac$，若 $(b,c)=1$，求证： $b \mid a$ 。

   Proof

   应用算术基本定理分解质因数可证。

4. 设 $(a,b)=1$，求证：$(a^2+b^2,ab)=1$ 。

   Proof

   要证 $(a^2+b^2,ab)=1$，即证 $(a^2+b^2+2ab,ab)=1$，即证 $((a+b)^2,ab)=1$，只需证 $(a+b,ab)=1$。

   设 $(a+b,ab)$ 的最大素因子为 $p$，下面证明 $p=1$。

   由 $p \mid (a+b,ab)$，则 $p \mid ab$，进而 $p \mid a$ 和 $p \mid b$ 至少有一个成立。不妨设 $p \mid a$ 成立。则由于 $p \mid a+b$，则 $p \mid b$ 也一定成立。

   因此 $p \mid (a,b)$，结合 $(a,b)=1$， 便可知 $p \mid 1$，因此只能有 $p=1$，即 $(a+b,ab)=1$。

5. 设正整数 $a,b,c$ 的最大公因数为 $1$，并且 $\dfrac{ab}{a-b}=c$，求证：$a-b$ 是一个完全平方数。

   Proof

   由题设条件可推出 $(a-b)(c-b)=b^2$ 以及 $a>b,c>b$ 。

   设 $(a,b)=d$ 及 $a=a_1 d,b =b_1 d$ ，进而 $(a_1,b_1)=1$ 和 $(d,c)=1$ 。

   于是 $(a-b)(c-b)= d(a_1 -b_1)(c-b)=b_1^2 d^2$，即

   $$(a_1 - b_1)(c-b_1 d)=b_1^2 d$$

   由于 $b_1^2 \mid b_1^2 d \implies b_1^2 \mid (a_1-b_1)(c-b_1d) $ 。由 $(a_1,b_1)=1$ 可推知 $(a_1-b_1,b_1^2)=1$ ，因此只能 $b_1^2 \mid (c-b_1 d)$ ，进而 $c-b_1 d=mb_1^2 \,(m\ge 1)$。同理，有 $d \mid a_1 - b_1$ ，进而 $a_1-b_1 = n d \, (n \ge 1)$ 。代回上式，得到

   $$mn=1$$

   因此只能有 $m=n=1$ 。于是 $d=b_1^2, a_1-b_1=d$ 。

   于是 $a-b = (a_1 - b_1)d = d^2$ 是完全平方数。

6. 两种不同面值 $a,b$ 的硬币，满足 $a,b$ 互素，硬币数量不限，求证：它们不能组合出的最大面额是 $ab-a-b$ 。例如，$3$ 元和 $7$ 元不能支付的价格有 $1,2,4,5,8,11$ 元，所以不能组合出的面额中最大是 $11$ 元。^{[5] [6]}

   Proof

   由于 $(a,b)=1$，由推论2，不定方程 $ax+by=c$ 必定有整数解。设 $x_0,y_0$ 为该方程的一组特解，则方程的所有解可以表示为

   $$\left\{\begin{matrix} x=x_0 +bt\\ y=y_0 - at \end{matrix}\right. \qquad t=0,\pm 1,\pm2,\cdots$$

   则非负解为 $x=x_0+bt \ge 0, y=y_0-at \ge 0$，故有 $-\dfrac{x_0}{b} \le t \le \dfrac{y_0}{a}$。又 $t \in \Z$，故有 $-\left[\dfrac{x_0}{b}\right] \le t \le \left[\dfrac{y_0}{a}\right]$，即 $t$ 可以取下列值：

   $$-\left [ \frac{x_0}{b} \right ], -\left [ \frac{x_0}{b} \right ]+1,\cdots,0,1,\cdots,\left [ \frac{y_0}{a} \right ]$$

   因此不定方程 $ax+by=c$ 的非负解的组数为 $N_0=\left[ \dfrac{x_0}{b} \right ] + \left [ \dfrac{y_0}{a} \right ] +1$ 。又 $\left[ \dfrac{x_0}{b} + \dfrac{y_0}{a} \right ]\le \left[ \dfrac{x_0}{b} \right ] + \left [ \dfrac{y_0}{a} \right ] +1$ 及 $\left[ \dfrac{x_0}{b} \right ] + \left [ \dfrac{y_0}{a} \right ] \le \left[ \dfrac{x_0}{b} + \dfrac{y_0}{a} \right ]$，故

   $$\left[ \frac{x_0}{b} + \frac{y_0}{a} \right ] \le N_0 \le \left[ \frac{x_0}{b} + \frac{y_0}{a} \right ]+1$$

   且上式的两个等号有且仅有一个成立。由于 $x_0,y_0$ 是不定方程 $ax+by=c$ 的特解，故 $a x_0+b y_0 =c$，所以 $\dfrac{x_0}{b} + \dfrac{y_0}{a} = \dfrac{c}{ab}$ 。故

   $$N_0 = \left[ \frac{c}{ab} \right] \quad or \quad N_0 = \left[ \frac{c}{ab} \right]+1$$

   当 $c>ab-a-b$ 时，有

   $$\begin{aligned} 1-\frac{1}{a} - \frac{1}{b} < \frac{c}{ab} &= \frac{x_0}{b} + \frac{y_0}{a}=\left [ \frac{x_0}{b} \right ]+\left \{ \frac{x_0}{b} \right \} + \left [ \frac{y_0}{a} \right ]+\left \{ \frac{y_0}{a} \right \} \\ &= \left [ \frac{x_0}{b} \right ]+ \left [ \frac{y_0}{a} \right ]+\left \{ \frac{x_0}{b} \right \} +\left \{ \frac{y_0}{a} \right \} \\ &\le \left [ \frac{x_0}{b} \right ]+ \left [ \frac{y_0}{a} \right ]+\frac{b-1}{b}+ \frac{a-1}{a} \end{aligned}$$

   即 $1<\left [ \dfrac{x_0}{b} \right ]+ \left [ \dfrac{y_0}{a} \right ]+2$，即

   故有 $N_0>0$，即这时必有非负解。

   当 $c=ab-a-b$ 时，用反证法证明方程 $ax+by=ab-a-b$ 无非负解。若有非负解 $x_1,y_1$ ，即 $ax_1+by_1=ab-a-b$ ，则 $ab=a(x_1+1)+b(y_1+1)$，由于 $(a,b)=1$，则必有 $a\mid (y_1+1)$， $b\mid (x_1+1)$，得 $y_1+1 \ge a, x_1 + 1 \ge b$ 。故

   $$ab=a(x_1+1)+b(y_1+1) \ge ab+ab \ge 2ab$$

   矛盾，因此当当 $c=ab-a-b$ 时，不定方程 $ax+by=c$ 无非负解。

   此题在NOI中也可使用扩展欧几里德算法，详细见OI Wiki。

最小公倍数

定义

设 $a_1,a_2,\cdots,a_n$ 是 $n$ 个整数。若整数 $m$ 是它们之中每一个的倍数，则 $m$ 就叫做 $a_1,a_2,\cdots,a_n$ 的一个公倍数。在一切公倍数中最小的正数叫做最小公倍数，记作 $\operatorname{lcm} (a_1,a_2,\cdots,a_n)$。在不引起混淆的情况下，简记为 $[a_1,a_2,\cdots,a_n]$。

最小公倍数的英文是 Least Common Multiple，这就是缩写为 $\mathrm{lcm}$ 的原因。

定理

两个整数 $a,b$ 的最大公因数和最小公倍数满足

$$(a,b)[a,b]=|ab|$$

性质

• $a,b$ 的任一公倍数都是 $[a,b]$ 的倍数；
• 若 $a_1, a_2, \cdots ,a_n$ 两两互素，则有

$$[a_1,a_2,\cdots,a_n] = |a_1 a_2 \cdots a_n|$$

素数

定义

一个大于 $1$ 的整数，如果它的正因数只有 $1$ 和它本身，就叫做素数。否则叫做合数。

性质

• 设 $n$ 是大于 $1$ 的整数，则 $n$ 的除 $1$ 以外的最小正因数 $q$ 是素数。
• 设 $p$ 是素数，$n$ 是任意一个整数，则要么 $p \mid n$，要么 $(p,n)=1$ 。
• 设 $p$ 是素数，$a,b$ 是整数，$p \mid ab$，则 $p \mid a$ 或 $p \mid b$ 。特别地，若 $p \mid a^n$，则 $p \mid a$ 。

算术基本定理 / 唯一分解定理

任意一个大于 $1$ 的整数 $n$ 能够唯一地分解为

$$n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$$

其中 $p_i<p_j (i<j)$ 是素数。

并且 $n$ 的全部正约数为

$$d =p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k} \> (\alpha_i \ge \beta_i \ge 0)$$

素数的判定

考虑因数成对出现，因此只需判定 $[1,\sqrt{a}]$ 即可。

bool isPrime(a) {
  if (a < 2) return 0;
  for (int i = 2; i * i <= a; ++i)
    if (a % i == 0) return 0;
  return 1;
}

素数的分布

素数有无穷多个

用反证法证明。假设素数只有有限多个，设全体素数为 $p_1,p_2, \cdots, p_k$ 。考虑数 $N=p_1 p_2 \cdots p_k +1$ 。显然 $N>1$，于是根据第一条性质，取它的最小正因数 $p>1$，则一定有 $p \in \{p_1,p_2, \cdots, p_k\}$。于是 $p\mid p_1 p_2 \cdots p_k$，又因为 $p \mid (p_1 p_2 \cdots p_k+1)$，所以 $N$ 和 $N-1$ 有公因数 $p$，这与 $N$ 与 $N-1$ 互素矛盾。

素数计数函数

素数计数函数是一个用来表示小于或等于某个实数 $x$ 的素数的个数的函数，记作 $\pi(x)$ 。

当 $x \rarr +\infty$ 时，$\pi(x) \sim \dfrac{x}{\ln x}$ 。

埃拉托斯特尼筛法

要得到自然数 $n$ 以内的全部素数，必须把不大于 $\sqrt{n}$ 的所有素数的倍数剔除，剩下的就是素数。

int n;
vector<char> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i * i <= n; i++) {
  if (is_prime[i]) {
    for (int j = i * i; j <= n; j += i) is_prime[j] = false;
  }
}

例题

1. 求证：对于任意给定的正整数 $n>1$，都存在连续 $n$ 个合数。

   Proof

   由于 $4(9n+4)-3(12n+5)=1$，所以 $12n+5$ 和 $9n+4$ 互素。

   /* ax+by=1 判断互素是锐利的性质 */

2. 若整数 $a,b$ 满足 $2a^2+a=3b^2+b$，求证： $a-b$ 和 $2a+2b+1$ 都是完全平方数。^[7]

3. 求证：两个连续正整数之积不能是完全平方，也不能是完全立方。^[8]

同余

定义

设 $n$ 是给定的正整数，若整数 $a,b$ 满足 $n \mid (a,b)$，则称 $a$ 和 $b$ 模 $n$ 同余，记作

$$a \equiv b \pmod n$$

若 $n \nmid (a-b)$，则称 $a$ 和 $b$ 模 $n$ 不同余，记作

$$a \not\equiv b \pmod n$$

性质

• 反身性：$a \equiv a \pmod n$
• 对称性：若 $a \equiv b \pmod n$，则 $b \equiv a \pmod n$
• 传递性：若 $a \equiv b \pmod n$，$b \equiv c \pmod n$，则 $a \equiv c \pmod n$
• 同余式相加：若 $a \equiv b \pmod n$，$c \equiv d \pmod n$，则 $a \pm c \equiv b \pm d \pmod n$
• 同余式相乘：若 $a \equiv b \pmod n$，$c \equiv d \pmod n$，则 $ac \equiv bd \pmod n$
• 互素消去律：若 $ac \equiv bc \pmod n$，且 $(c,n)=1$，则 $a \equiv b \pmod n$

推论

• 若 $a \equiv b \pmod m$，则 $(a,m)=(b,m)$
• 设 $p$ 是素数，则 $(a+b)^p \equiv a^p +b^p \pmod m$
• 由二项式定理，$a^n \equiv (a-mk)^n \pmod m$

例题

1. 设 $A$ 是十进制数 $4444^{4444}$ 的个位数字之和，$B$ 是 $A$ 的各位数字之和，求 $B$ 的个位数字之和。^[9]

   Proof

   先证明一个引理：十进制数模 $9$ 与各位数字之和模 $9$ 同余。

   设 $n = \overline{a_k a_{k-1} \cdots a_1 a_0}$，则 $n = a_0 + a_1 10^1 +\cdots + a_{k-1} 10^{k-1} + a_k 10^k$ ，且 $n$ 的各位数字之和 $S(n)=a_0 + a_1 + \cdots + a_{k-1} + a_k$ 。令函数 $f(x) = a_0 + a_1 x^1 + \cdots a_k x^k$ ，由于 $10 \equiv 1 \pmod 9$ ，因此 $f(10) \equiv f(1) \pmod 9$ ，即 $n \equiv S(n) \pmod 9$ 。

   因此 $4444^{4444} \equiv A \equiv B \equiv S(B) \pmod 9$ 。下面估计 $S(B)$ 的数量级。

   $$4444^{4444} < \left(\frac{10^4}{2}\right)^{4444} = \frac{10^{17776}}{2^{4444}}$$

   注意到 $2>\sqrt[4]{10}$ ，因此 $\lg 2 > 1/4$ 。对上面不等式取对数，得到

   $$\lg 4444^{4444} < 17776-4444\lg 2 <17776-1111=16665$$

   因此 $4444^{4444}$ 不超过 $16665$ 位，假设各个数位上全都是 $9$ ，则 $A<16665 \times 9 = 149985$ ；取 $A$ 为 $139999$ ，则 $B\le 40$ ；取 $B=39$ ，则 $S(B) \le 12$ 。

   再考虑

   $$4444^{4444} \equiv (-2)^{4444} \equiv 2^{1481\times3+1}\equiv 2 \cdot8^{1481} \equiv -2 \equiv 7 \pmod 9$$

   因此 $S(B)$ 只能为 $7$ 。

2. 求证：对于任意自然数 $n$，$1^{1987}+2^{1987}+\cdots+n^{1987}$ 不能被 $n+2$ 整除。

   Proof

   证明：注意到 $1987$ 是一个素数，利用推论 $2$

   $$\begin{aligned} 1^{1987}+2^{1987}+\cdots+n^{1987} &\equiv \frac{1}{2} \left[ 1+1+ (n+2)^{1987} + (n-1+3)^{1987} + \cdots + (2+n)^{1987} \right] \\ &\equiv 1+\frac{n-1}{2}(n+2)^{1987}\\ &\equiv 1 \pmod{n+2} \end{aligned}$$

   因此 $1^{1987}+2^{1987}+\cdots+n^{1987}$ 不能被 $n+2$ 整除。

---

1. K.R. (2010, July 28). \mid, | (vertical bar), \vert, \lvert, \rvert, \divides. TeX - LaTeX Stack Exchange. https://tex.stackexchange.com/questions/498/mid-vertical-bar-vert-lvert-rvert-divides ↩︎

2. 余红兵. (2012). 数论 (2nd ed., Vol. 3). 华东师范大学出版社. ↩︎

3. 柯召., & 孙琦. (2001). 数论讲义 (3rd ed., Vol. 3). 高等教育出版社. ↩︎

4. OI Wiki. (2021, February 8). 裴蜀定理 - OI Wiki. https://oi-wiki.org/math/bezouts/ ↩︎

5. CCF NOI竞赛委员会. (2017, November 11). [NOIP2017 提高组] 小凯的疑惑 - 洛谷. 洛谷. https://www.luogu.com.cn/problem/P3951 ↩︎

6. 张君达. 数论基础[M]. 北京科学技术出版社, 2002: 86-87. ↩︎

7. 余红兵. (2012). 素数及唯一分解定理. In 数论 (2nd ed., p. 15). 华东师范大学出版社. ↩︎

8. 余红兵. (2012). 不定方程. In 数论 (2nd ed., pp. 20–21). 华东师范大学出版社. ↩︎

9. 张君达. 数论基础[M]. 北京科学技术出版社, 2002: 110-111. ↩︎