a folklore in the Mathematical Olympiad
首先我们定义$a=v_p(x)$表示最大的数$a$使得$p^a|x$，其中$p$是素数
容易知道以下性质：
$$v_p(xy)=v_p(x)+v_p(y)$$
$$v_p(x+y) \geq max(v_p(x),v_p(y))$$
下面介绍LTE定理(Lifting The Exponent Lemma)：
对于奇素数$p$，正整数$n$和整数$x,y$，且$p|x-y$，$p \nmid x$有
$$v_p(x^n-y^n) = v_p(x-y) + v_p(n) \quad(1)$$
特别的，对于正奇数$n$，$p|x+y$有
$$v_p(x^n + y^n) = v_p(x+y) + v_p(n) \quad (2)$$
当$p=2$时，若$4|x-y$，$(1)(2)$均成立
当$p=2$且$2|x-y$时，有
$v_2(x^n - y^n) = v_2(x-y) + v_2(x+y) + v_2(n) - 1 \quad (3)$
下面写出证明
对于$(1)$式，我们首先有
$$\begin{array}{}v_p(x^n - y^n) &= v_p((x-y)(x^{n-1} + x^{n-2}y + \cdots y^{n - 1}))\ &= v_p(x-y) + v_p(x^{n-1} + x^{n-2}y + \cdots y^{n - 1})\end{array} $$
当$p \nmid n$时，显然$x^{n-1} + x^{n-2}y + \cdots y^{n - 1} \equiv nx^{n-1}\quad (mod ; p)$
因此$v_p(x^{n-1} + x^{n-2}y + \cdots y^{n - 1}) = v_p(n)+v_p(x^{n - 1} )= 0\quad (4)$
当$p | n$时，先证明$v_p(x^p-y^p) = v_p(x-y) + 1 \quad (5)$
即证明$v_p(x^{p - 1} + x^{p - 2} y + \cdots y^{p - 1}) = 1$
由$x^{p-1} + x^{p-2}y + \cdots y^{p - 1} \equiv px^{p-1}\equiv 0\quad(mod;p)$，显然$v_p(x^{p - 1} + x^{p - 2} y + \cdots y^{p - 1}) \geq 1$
下证$v_p(x^{p - 1} + x^{p - 2} y + \cdots y^{p - 1}) = 2$不成立，即证$p^2 \nmid (x^{p - 1} + x^{p - 2} y + \cdots y^{p - 1})$
因为$p|x-y$，不妨假设$x < y,y = kp+x,t \in [1, p-1],t \in Z $
$$\begin{array}{}x^{p - 1 - t} y^t & \equiv x^{p-1-t}(kp+x)^t&\quad (mod; p^2)\\ & \equiv x^{p-1} + tkpx^{p-2} &\quad (mod; p^2)\end{array} $$
所以
$$\begin{array}{}(x^{p - 1} + x^{p - 2} y + \cdots y^{p - 1}) &\equiv px^{p-1} + (1+\cdots + (p - 1))kpx^{p-2} &\quad (mod; p^2)\ &\equiv px^{p-1} + \frac{p-1}2 kp^2x^{p-2} (6) &\quad (mod; p^2)\quad\ &\equiv px^{p - 1}&\quad (mod; p^2)\end{array}$$
因为$p\nmid x$，所以$p^2 \nmid (x^{p - 1} + x^{p - 2} y + \cdots y^{p - 1})$，所以$v_p(x^{p - 1} + x^{p - 2} y + \cdots y^{p - 1}) = 1$
由$(5)$，设$n=p^ab$，其中$p\nmid b$，我们有
$$v_p(x^n-y^n) = v_p(x^{(p^{a-1})p} - y^{(p^{a-1})p}) = v_p(x^{p^{a-1}} - y^{p^{a-1}}) + 1$$
递归下去，且由$(4)$式子，我们有
$$v_p(x^n - y^n) = v_p(x^b - y^b) + b = v_p(x-y) +v_p(n)$$
$(1)$式证毕
对于$(2)$式，因为$n$是正奇数，不妨令$y=-y$
$ v_p(x^n + (-y)^n) = v_p(x^n-y^n) = v_p(x-y) + v_p(n)$
即$v_p(x^n+y^n) = v_p(x+y)+v_p(n)$
对于$p=2$，注意到$\frac{p-1} 2k$不一定是整数，若$2|k$，即$4|x-y$,$(1)$式仍成立，即
$$v_2(x^n-y^n) = v_2(x-y) + v_2(n)$$
若$2|x-y$，注意到$x,y$都是奇数，且$4|(x^2-y^2)$，令$n=2^ab$我们有
$$v_2(x^n-y^n) = v_2((x^2)^{2^{a-1}b}-(y^2)^{2^{a-1}b}) = v_p(x+y)+v_p(x-y)+v_p(n) - 1$$
至此，LTE定理证毕
下面丢出例题
$Reference:$