Tongrui 4 数论【施工中】
Published:
二次剩余
TODO: 文章
来自 Example 4.12：当 $p \bmod 4 = 3$ 时，$-1^2, -2^2, \cdots, -(\frac {p-1} 2)^2$ 构成全部的非二次剩余。
Hensel 版 Newton 迭代
若能找到 $x_k$ 使得：
\[\begin{cases} f(x_k) \equiv 0 \pmod {p^k} \\ f'(x_k) \not \equiv 0 \pmod {p^k} \\ \end{cases}\]则
\[x_{k+1} \equiv x_k - \frac {f(x_k)} {f'(x_k)} \pmod {p^{k+1}}\]TODO:
Dirichlet 定理
对于互质正整数 $a \perp m$，存在无数个质数 $p$ 满足
\[p \equiv a \pmod m\]且满足这一条件的质数占所有质数的 $\frac 1 {\varphi(m)}$。
严谨地说，令比值 $r(x)$ 为「$\le x$ 的满足条件的质数个数」与「$\le x$ 的质数个数」之比，则 $\lim_{x \to \infty} r(x) = \frac 1 {\varphi(m)}$。
Lucas 定理
通过二项式定理可以证明：
\[(1 + x)^p \equiv 1 + x^p \pmod p\]反复套用，可以归纳出：
\[(1 + x)^{p^k} \equiv 1 + x^{p^k} \pmod p\]考虑对 $(1 + x)^n$ 作 $p$ 进制拆分：
\[\begin{aligned} (1 + x)^n & \equiv \prod (1 + x)^{n_i \times p^i} \pmod p \\ (1 + x)^n & \equiv \prod (1 + x^{n_i \times p^i}) \pmod p \\ [x^m] (1 + x)^n & \equiv \prod [x^{m_i}] (1 + x^{n_i \times p^i}) \pmod p \\ \binom n m & \equiv \prod \binom {n_i} {m_i} \pmod p \end{aligned}\]Kummer 定理
\[\nu_p(n!) = \sum_{k=1}^\infty \left\lfloor \frac n {p^k} \right\rfloor\] \[\begin{aligned} \nu_p(\binom {n+m} n) &= \nu_p((n+m)!) - \nu_p(n!) - \nu_p(m!) \\ &= \sum_{k=1}^\infty \left( \left\lfloor \frac {n+m} {p^k} \right\rfloor - \left\lfloor \frac n {p^k} \right\rfloor - \left\lfloor \frac m {p^k} \right\rfloor\right) \\ &= \sum_{k=1}^\infty [p \text{ 进制计算 } n+m \text{ 时第 } k \text{ 位被进位}] \\ &= p \text{ 进制计算 } n + m \text{ 的总进位次数} \\ &= p \text{ 进制计算 } (n + m) - n \text{ 的总退位次数} \\ \end{aligned}\]Pell 方程
结论：方程
\[x^2 - D y^2 = 1\]（其中 $D$ 不是完全平方数）的所有正整数解满足
\[x_n + y_n \sqrt D = (x_1 + y_1 \sqrt D)^n\]注意这是一个线性递推。
$x_1, y_1$ 在 $D$ 较小的时候可以暴力寻找。更优雅的做法是通过 $\sqrt D$ 的连分数展开的截断，此处不展开。
一个比较好的讲解视频：【乐正垂星】连分数，佩尔方程，和曲线上的有理点
Frobenius coin problem
有若干种面值为 $a_1, \cdots, a_n$ 的硬币，每种硬币可以无限次使用。研究这些硬币组合出的价格的性质。
$2$ 种硬币
对于面值为 $p,q$ 的两种硬币：
\[\boxed{ k \text{ is expressible} \iff (pq - p - q) - k \text{ is not expressible} }\]- 无法被表示出的最大价格为 $pq - p - q$。P3951 [NOIP 2017 提高组] 小凯的疑惑
- 无法被表示出的价格数量为 $\frac {(p-1) (q-1)} 2$。
证明略去。
多种硬币
练习题：AMC12B 2023 #16
多种硬币没有很好的性质。
「无法被表示的最大价格」「无法被表示出的价格数量」都可以通过同余最短路得到。
硬币组合化简
对于一组硬币 $a_1, \cdots, a_n$，我想求一组数量最少的硬币 $b_1, \cdots, b_m$（$m \le n$），使得它们能够组合出的价格相同（即 $a$ 能组合出的 $b$ 也能组合出，$a$ 不能组合出的 $b$ 也不能组合出）。
结论：$b$ 是 $a$ 的子集——对于 $a$ 中的一个元素，如果它能被其他元素表示出就扔掉，否则留着。
证明略去。
圆上的整点
Diophantine 方程
\[x^2 + y^2 = N\]有整数解的充要条件为：在 $N$ 的质因数分解中，对于每个 $\bmod 4 = 3$ 的质数 $p$，都有 $2 \mid \nu_p(N)$。
省略的题目
- Example 4.9 纯 Ad-hoc，没有借鉴价值。
- Example 4.19 过简单。
- Example 4.23 与 Example 4.24 重复。
- Example 4.29 结合了 Frobenius coin problem 的纯粹的分类讨论 Ad-hoc。
Example 4.1 2010 UKMT NST Day 2 #1
定义 Lucas 数列
\[L_n = \begin{cases} 2 & n = 0 \\ 1 & n = 1 \\ L_{n-1} + L_{n-2} & n \ge 2 \\ \end{cases}\]证明：若质数 $p \mid (L_{2k} - 2)$，则 $p \mid (L_{2k+1} - 1)$。
ANSWER NOT FOUND
Example 4.2-4.7
TODO:
Example 4.8 AIME II 2008 #15 (Easy)
\[\begin{cases} n^2 = 3 a^2 + 3a + 1 \\ 2n + 79 = b^2 \\ \end{cases}\]正整数 $n$ 同时满足：
- $n^2$ 是两个连续立方数的差。
- $2n$ 是一个完全平方数减 $79$。
求最大的 $n$。
把 $n$ 消掉，配方：
\[(b^2 - 79)^2 - 3 (2a+1)^2 = 1\]因为这是一道 AIME 题有 $n < 1000$，求出该 Pell 方程最小的几个解即可。答案为 $\boxed{181}$。
严谨证明
TODO:
Example 4.10 MPFG 2022 #4 (Easy, Ad-hoc)
\[n^3 \equiv 1 \pmod {103}\]提示：$10^2 + 3 = 103$。
排掉 $n \equiv 1$ 的平凡解。
\[n^2 - n + 1 \equiv 0 \pmod {103}\] \[n \equiv \frac {1 \pm \sqrt{-3}} 2\]根据提示，注意到 $\pm 10$ 是 $-3$ 的二次剩余（$103 = (\pm 10)^2 + 3$）。
\[\frac 1 2 \equiv 52 \pmod {103}\]因此答案为 $\boxed{n \equiv 1, 46, 56 \pmod {103}}$。
Example 4.11 MPFG 2023 #10 (Easy, Ad-hoc)
\[n^3 \equiv 3 \pmod {4099}\]为了减少你的计算量，可以告诉你 $4099$ 是质数。
提示：
- $16^3 + 3 = 4099$。
- $64^2 + 3 = 4099$。
根据提示，$-16$ 是一个解。
\[(\frac n {-16})^3 \equiv 1 \pmod {4099}\]令 $u = \frac n {-16}$。
\[u^2 + u + 1 \equiv 0 \pmod {4099}\]然后发现数字又凑好了，把上题的解法抄一遍。答案为 $\boxed{n \equiv 520,3595,4083 \pmod {4099}}$。
Example 4.12 MPFG 2018 #18 (Hard)
\[\left\lvert \prod_{k=0}^{15} (1 + \omega_{31}^{k^2}) \right\rvert\]提示：$31$ 是质数且 $31 \bmod 4 = 3$。
令 $p = 31$。
二次剩余题。
首先简化问题，把加单位根改成减单位根，并且单独摘出 $k=0$：
\[\left\lvert \prod_{k=0}^{\frac {p-1} 2} (1 + \omega_p^{k^2}) \right\rvert = 2 \left\lvert \prod_{k=1}^{\frac {p-1} 2} (-1 - \omega_p^{k^2}) \right\rvert\]求模长，考虑构造共轭（$\lvert z \rvert = \sqrt{z \bar z}$）：
\[\begin{aligned} & \left\lvert \prod_{k=1}^{\frac {p-1} 2} (-1 - \omega_p^{k^2}) \right\rvert \\ =& \sqrt{\prod_{k=1}^{\frac {p-1} 2} (-1 - \omega_p^{k^2}) \times \prod_{k=1}^{\frac {p-1} 2} (-1 - \omega_p^{- k^2})} \end{aligned}\]$k^2$ 是二次剩余，那 $-k^2$ 呢？由 Euler’s criterion 可知：
\[\left( \frac {-1} p \right) \equiv (-1)^{\frac {p-1} 2} = -1 \pmod p\]（此处使用了 $p \bmod 4 = 3$）所以 $-1$ 不是 $\bmod p$ 下的二次剩余。
我们知道 $1^2, 2^2, \cdots, (\frac {p-1} 2)^2$ 构成全部二次剩余，因此 $-1^2, -2^2, \cdots, -(\frac {p-1} 2)^2$ 构成全部的非二次剩余。
而二次剩余和非二次剩余构成 $1, \cdots, p-1$ 之间的所有数：
\[\begin{aligned} & \sqrt{\prod_{k=1}^{\frac {p-1} 2} (-1 - \omega_p^{k^2}) \times \prod_{k=1}^{\frac {p-1} 2} (-1 - \omega_p^{- k^2})} \\ =& \sqrt{\prod_{k=1}^{p-1} (-1 - \omega_p^k)} \\ =& \sqrt{\frac {(-1)^p - 1} {(-1) - 1}} \\ =& 1 \\ \end{aligned}\]因此答案为 $2 \times 1 = \boxed{2}$。
Example 4.13
ANSWER NOT FOUND
Example 4.14 AIME I 2016 #12 (Normal)
求使得 $\Omega(m^2 - m + 11) \ge 4$ 的最小正整数 $m$。
设 $p$ 为 $m^2 - m + 11$ 的一个质因子。
首先这题看着就像个二次剩余题，看看能不能排除掉 $p=2$。验一下发现 $m^2 - m + 11$ 一定是奇数，那确实能排掉。
配方：
\[\begin{aligned} m^2 - m + 11 &\equiv 0 \pmod p \\ (2m - 1)^2 &\equiv - 43 \pmod p \\ \end{aligned}\]也就是说 $(\frac {-43} p) = 1$。这里用二次互反律就麻烦了，直接枚举一下 $p$ 检验，可能的 $p$ 有：$11,13,17,23,\cdots$
不妨猜最小的情况确实只有 $4$ 个质数 $p_1, p_2, p_3, p_4$。同余方程联立合一下：
\[(2m-1)^2 = 4 p_1 p_2 p_3 p_4 - 43\]Take a leap of faith——相信出题人不会在这里坑害你。枚！举！得出 $p_1 = p_2 = p_3 = 11, p_4 = 13$ 直接解得答案为 $\boxed{132}$。
Example 4.15
ANSWER NOT FOUND
Example 4.16 AIME I 2018 #11 (Easy)
求方程的最小正整数解：
\[3^n \equiv 1 \pmod {143^2}\]
喜闻乐见 CRT：
\[\begin{cases} 3^n \equiv 1 \pmod {11^2} \\ 3^n \equiv 1 \pmod {13^2} \\ \end{cases}\]升幂计算两个阶：
\[\begin{aligned} & \text{ord}_{11}(3) = 5, \nu_{11}(3^5 - 1) = 2 \\ & \implies \text{ord}_{11^2}(3) = \text{ord}_{11}(3) = 5 \\ \end{aligned}\] \[\begin{aligned} & \text{ord}_{13}(3) = 3, \nu_{13}(3^3 - 1) = 1 \\ \implies & \text{ord}_{13^2}(3) = \text{ord}_{13}(3) \times 13^{2-1} = 39 \\ \end{aligned}\]答案为 $\text{lcm}(5, 39) = \boxed{195}$。
Example 4.17 AIME I 2019 #14 (Easy)
\[\begin{aligned} 2019^8 & \equiv -1 \pmod p \\ 2019^{16} & \equiv 1 \pmod p \\ \text{ord}_p(2019) & = 16 \\ 16 & \mid \varphi(p) \\ 16 & \mid (p-1) \\ \end{aligned}\]求 $2019^8 + 1$ 的最小奇质因子。
枚举。$p = 17$ 不对，$p = \boxed{97}$ 对了。
Example 4.18 AIME I 2024 #13 (Hard)
\[\begin{aligned} n^4 \equiv -1 \pmod {p^2} \\ n^8 \equiv 1 \pmod {p^2} \\ \text{ord}_{p^2}(n) = 8 \\ 8 \mid \varphi(p^2) \\ 8 \mid p (p-1) \\ \end{aligned}\]$p$ 为最小的满足「存在正整数 $n$ 使得 $p^2 \mid (n^4 + 1)$」的质数。
求出使得 $p^2 \mid (n^4 + 1)$ 成立的最小正整数 $n$。
第一个满足条件的是 $p = 17$。我们来检验一下（剧透：$17$ 确实是对的）。
我们要求 $-1$ 的四次剩余，即求 $\omega_8^1, \omega_8^3, \omega_8^5, \omega_8^7$。能解得任何一个，就可以直接得到另外 $3$ 个。
以下两种方法中，不管哪一个都需要首先解出 $\bmod 17$（而不是 $\bmod 17^2$）下该方程的解：
\[r_0^4 \equiv -1 \pmod {17}\]解为 $r_0 = \pm 2, \pm 8$。
Sol 1：LTE 的人类智慧
不妨就用 $2$ 好了。通过 LTE 来凑个答案。我们猜测答案形如 $2^k$。为了使 LTE 可以使用，需要 $k$ 是奇数。
\[\begin{aligned} \nu_{17}((2^k)^4 + 1) \ge 2 \\ \nu_{17}((2^4)^k + 1) \ge 2 \\ \nu_{17}(2^4 + 1) + \nu_{17}(k) \ge 2 \\ \end{aligned}\]取 $k = 17$：
\[\begin{aligned} (2^{17})^4 \equiv -1 \pmod {17^2} \\ \omega_8 \equiv 2^{17} \pmod {17^2} \\ \end{aligned}\]计算后，最小的是 $\omega_8^3 \equiv \boxed{110} \pmod {17^2}$。
Sol 2：Newton 迭代（Hensel 引理）
在 $f(r_0) \equiv 0 \pmod {17}$ 且 $f’(r)_0 \not \equiv 0 \pmod {17}$ 时：
\[r \equiv r_0 - \frac {f(r_0)} {f'(r_0)} \pmod {17^2}\]令 $f(x) = x^4 + 1$。直接算出四个答案为 $155, 134, \boxed{110}, 179$（途中需要 exgcd 求逆元）。
Example 4.20 AIME I 2020 #12 (Easy)
问题节选：求方程的最小正整数解
\[5^5 \mid (149^n - 2^n)\]
很想 LTE 但是不可以，因为 $5 \nmid (149 - 2)$。考虑怎么把它们转成整除。
\[\begin{aligned} 149^n & \equiv 2^n \pmod 5 \\ 2^n & \equiv 1 \pmod 5 \\ n & \equiv 0 \pmod 4 \end{aligned}\]问题变为
\[5^5 \mid ((149^4)^{\frac n 4} - (2^4)^{\frac n 4})\]此时可以 LTE。后面略。
Example 4.21 AIME I 2021 #14 (Normal)
对于任意正整数 $a$ 有
\[2021 \mid (\sigma(a^n) - 1)\]求 $n$ 的最小值。
$\sigma$ 是积性函数：
\[\sigma(a^n) = \prod_{p^k \mid a} \frac {p^{nk +1} - 1} {p - 1}\]若对任意质数幂 $p^k$ 成立，则对任意数 $a$ 成立：
\[\frac {p^{nk +1} - 1} {p - 1} \equiv 1 \pmod {2021}\]特判掉 $p - 1 \not \perp 2021$（一会儿再说）：
\[p^{nk+1} \equiv p \pmod {2021}\]特判掉 $p = 43, 47$（总是成立，无影响）：
\[(p^k)^n \equiv 1 \pmod {2021}\]CRT 拆开：
\[\begin{cases} (p^k)^n \equiv 1 \pmod {43} \\ (p^k)^n \equiv 1 \pmod {47} \\ \end{cases}\]模质数下必有原根，由 Dirichlet 定理可知必有质数能取到原根所在的同余类。因此 $42 \mid n$ 且 $46 \mid n$。
回到 $p - 1 \not \perp 2021$ 的特殊情况，由 Dirichlet 定理可知 $p \equiv 1 \pmod {43}$ 和 $p \equiv 1 \pmod {47}$ 都存在。对于这类 $p$，有
\[\sigma(p^n) = n + 1\]因此 $43 \mid n$ 且 $47 \mid n$。
因此最小的 $n$ 为
\[n = \text{lcm}(42, 43, 46, 47) = 1952286\]输出 $\boxed{125}$。
Example 4.22 USAMO 2016 #2
对于正整数 $k$，证明这是一个整数：
\[(k^2)! \prod_{j=0}^{k-1} \frac {j!} {(j+k)!}\]
TODO: 感觉 AMC 某年 25 出过
Example 4.24 MPFG 2014 #18 (Easy)
\[\sum_{k=0}^{2014} [4 \mid \binom {2014} k]\]
根据 Kummer 定理，条件等价于二进制下 $2014 - k$ 产生的退位次数至少为 $2$。二进制下 $2014_{10} = 11111011110_2$。
正难则反，考虑退位次数不到 $2$ 的情况：
- $k \subseteq 2014$ 有 $2^9$ 种。
- $k$ 包含了恰好 $1$ 个 $0$ 的位置，且不包含这个 $0$ 前面的 $1$。有 $2^8 + 2^8$ 种。
共 $1024$ 种。答案为 $2015-1024=\boxed{991}$。
Example 4.25-4.27
TODO:
Example 4.28 (Hard)
TODO: 做过