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:
Lucas 定理和 Kummer 定理
\[(1 + x)^p \equiv 1 + x^p \pmod p\]TODO:
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.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$。
我一开始选择了二次互反律：
\[\begin{aligned} & \left( \frac {-43} p \right) \\ =& \left( \frac {-1} p \right) \left( \frac {43} p \right) \\ =& (-1)^{\frac {p-1} 2} \times (-1)^{\frac {p-1} 2 \times \frac {43-1} 2} \left( \frac p {43} \right) \\ =& \left( \frac p {43} \right) \end{aligned}\]即 $p$ 在 $\bmod 43$ 下是二次剩余。但是其实这样反倒不方便，因为我们需要的 $p$ 比 $43$ 小。
总之，枚举一下 $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.19
TODO:
Example 4.20-4.22
TODO:
Example 4.23
ANSWER NOT FOUND
Example 4.24 MPFG 2014 #18
\[\sum_{k=0}^{2014} [4 \mid \binom {2014} k]\]
TODO:
Example 4.25-4.27
TODO:
Example 4.28 (Hard)
TODO: 做过