升冪引理
內容
升冪（Lift the Exponent，LTE）引理是初等數論中比較常用的一個定理。
定義 \(v_p(n)\) 為整數 \(n\) 的標準分解中素因子 \(p\) 的冪次，即 \(v_p(n)\) 滿足 \(p^{v_p(n)}\mid n\) 且 \(p^{v_p(n)+1}\nmid n\).
由於升冪引理內容較長，我們將其分為三部分介紹：
以下內容設 \(p\) 為素數，\(x,y\) 為滿足 \(p\nmid x\) 且 \(p\nmid y\) 的整數，\(n\) 為正整數。
第一部分
對所有的素數 \(p\) 和滿足 \((n,p)=1\) 的整數 \(n\)，
-
若 \(p\mid x-y\)，則：
\[ v_p\left(x^n-y^n\right)=v_p(x-y) \] -
若 \(p\mid x+y\)，則對奇數 \(n\) 有：
\[ v_p\left(x^n+y^n\right)=v_p(x+y) \]
證明
若 \(p\mid x-y\)，則不難發現 \(p\mid x-y\iff x\equiv y\pmod p\)，則顯然有：
進而由 \(x^n-y^n=(x-y)\sum_{i=0}^{n-1}x^iy^{n-1-i}\) 可知命題得證。
對 \(p\mid x+y\) 的情況證明方法類似。
第二部分
若 \(p\) 是奇素數，
-
若 \(p\mid x-y\)，則：
\[ v_p\left(x^n-y^n\right)=v_p(x-y)+v_p(n) \] -
若 \(p\mid x+y\)，則對奇數 \(n\) 有：
\[ v_p\left(x^n+y^n\right)=v_p(x+y)+v_p(n) \]
證明
若 \(p\mid x-y\)，令 \(y=x+kp\)，我們只需證明 \(p\mid n\) 的情況。
-
若 \(n=p\)，則由二項式定理：
\[ \begin{aligned} \sum_{i=0}^{p-1}x^{p-1-i}y^i&=\sum_{i=0}^{p-1}x^{p-1-i}\sum_{j=0}^i\binom{i}{j}x^j(kp)^{i-j}\\ &\equiv px^{p-1} \pmod{p^2}\\ \end{aligned} \]從而
\[ v_p\left(x^n-y^n\right)=v_p(x-y)+1 \] -
若 \(n=p^a\)，則由數學歸納法可得
\[ v_p\left(x^n-y^n\right)=v_p(x-y)+a \]
因此命題得證。
對 \(p\mid x+y\) 的情況證明方法類似。
第三部分
若 \(p=2\) 且 \(p\mid x-y\)，
-
對奇數 \(n\) 有（與第一部分的 1 相同）：
\[ v_p\left(x^n-y^n\right)=v_p(x-y) \] -
對偶數 \(n\) 有：
\[ v_p\left(x^n-y^n\right)=v_p(x-y)+v_p(x+y)+v_p(n)-1 \]
另外對上述的 \(x,y,n\)，我們有：
若 \(4\mid x-y\)，則：
- \(v_2(x+y)=1\)
- \(v_2\left(x^n-y^n\right)=v_2(x-y)+v_2(n)\)
證明
我們只需證明 \(n\) 為偶數的情況。由於此時 \(p\nmid \dbinom{p}{2}\)，故我們不能用第二部分的方法證明。
令 \(n=2^a b\)，其中 \(a=v_p(n)\)，\(2\nmid b\)，從而
注意到 \(2\mid x-y\implies 4\mid x^2-y^2\)，從而 \((\forall i\geq 1),~~x^{2^i}+y^{2^i}\equiv 2\pmod 4\)，進而上式可變為：
因此命題得證。
參考資料
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用