升幂引理
Published:
$p$-adic 赋值的强三角不等式
\[\nu_p(x + y) \ge \min(\nu_p(x), \nu_p(y))\]取等条件为 $\nu_p(x) = \nu_p(y)$。
升幂：奇质数
对于
- $p$ 是奇质数
- $p \nmid a$
- $p \nmid b$
- $p \mid (a - b)$
变形：当 $n$ 是奇数时，把 $-b$ 代入 $b$：
\[\boxed{ \nu_p(a^n + b^n) = \nu_p(a + b) + \nu_p(n) }\]证明
\[a^n - b^n = b^n ((1 + \frac {a-b} b)^n - 1)\]设 $u = \frac {a - b} b$：
\[\nu_p(a^n - b^n) = \nu_p((1 + u)^n - 1)\] \[\begin{aligned} & (1 + u)^n - 1 \\ =& \sum_{k=0}^n \binom n k u^k - 1 \\ =& n u + \sum_{k=2}^n \binom n k u^k \\ \end{aligned}\]可以证明，此处 $u^2$ 及以上的项可以不看：
\[\nu_p((1 + u)^n - 1) = \nu_p(n u) = \nu_p(u) + \nu_p(n)\] \[\nu_p(a^n - b^n) = \nu_p(a - b) + \nu_p(n)\]为什么可以不看？
令 $a_k = \binom n k u^k$。对于 $k \ge 2$ 比大小：
\[\nu_p(a_k) \overset{?}{>} \nu_p(a_1)\]如果成立，则根据强三角不等式就能得到我们想要证的结论：
\[\nu_p\left(\sum_{k=1}^n a_k \right) = \nu_p(a_1)\]首先做一个放缩
\[\nu_p(\binom n k) = \nu_p(\frac n k \binom {n-1} {k-1}) \ge \nu_p(n) - \nu_p(k)\]（目的是为了能一会儿把 $\nu_p(n)$ 消掉，这样就与 $n$ 无关）
代进去之后再做一次放缩：
\[\begin{aligned} & \nu_p(\binom n k u^k) - \nu_p(nu) \\ \ge & (\nu_p(n) - \nu_p(k) + k \nu_p(u)) - (\nu_p(n) + \nu_p(u)) \\ =& (k-1) \nu_p(u) - \nu_p(k) \\ \end{aligned}\]第一项往小放到 $\nu_p(u) = 1$，第二项往大放到 $\log_p k$：
\[\begin{aligned} & (k-1) \nu_p(u) - \nu_p(k) \\ \ge & (k-1) - \log_p k \\ > & 0 \end{aligned}\]对于奇质数 $p$，在 $k \ge 2$ 上成立。
值得注意的是，当 $p = 2$ 且 $\nu_p(u) = 1$ 时，$k = 2$ 会让 $(k-1) \nu_p(u) - \nu_p(k)$ 恰好为 $0$，但这是后面才会聊的东西。
升幂：$p = 2$
对于
- $2 \nmid a$
- $2 \nmid b$
- 此时自动有 $2 \mid (a - b)$
$4 \mid (a - b)$ 或 $n$ 为奇数时，可以直接继承前面的结论：
\[\boxed{ \nu_2(a^n - b^n) = \nu_2(a - b) + \nu_2(n) }\]$n$ 为偶数时：
\[\boxed{ \nu_2(a^n - b^n) = \nu_2 \left( \frac {a^2 - b^2} 2 \right) + \nu_2(n) }\]证明
首先 $\nu_p(u) > 1$ 的时候（$4 \mid (a - b)$）怎么都不能把不等号卡成等号，所以可以直接套用之前的结论。
接下来只考虑 $\nu_p(u) = 1$。虽然第二项不能不看了，但是第三项及以上依然可以不看：
\[\begin{aligned} & \nu_2((1 + u)^n - 1) \\ =& \nu_2(nu + \binom n 2 u^2) \\ =& \nu_2(u) + \nu_2(n) + \nu_2(1 + \frac {n-1} 2 u) \\ =& \nu_2(u) + \nu_2(n) + \nu_2(b + (n - 1) \frac {a - b} 2) \end{aligned}\]在 $n$ 为奇数时后两项直接为 $0$：
\[\nu_2((1 + u)^n - 1) = \nu_2(u)\]当 $n$ 为偶数时，走二项式不太方便，选择直接套用 $4 \mid (a - b)$ 的情况：
\[\begin{aligned} & \nu_2(a^n - b^n) \\ =& \nu_2((a^2)^{\frac n 2} - (b^2)^{\frac n 2}) \\ =& \nu_2(a^2 - b^2) + \nu_2(\frac n 2) \\ \end{aligned}\]得证。