大家好，欢迎来到IT知识分享网。
一、升幂定理
引入记号 v p ( n ) v_p(n) vp(n) 表示 n n n 的唯一分解中 p p p 的次数，即 p v p ( n ) ∣ n p^{v_p(n)}\mid n pvp(n)∣n 且 p v p ( n ) ∤ n p^{v_p(n)}\nmid n pvp(n)∤n 。
升幂定理分为两种情况，模数为奇质数和模数为 2 2 2 。
① 模数为奇质数时，定理内容为：
n n n 为正整数，整数 p ∤ x , p ∤ y p\nmid x,p\nmid y p∤x,p∤y，且 x ≡ y ( m o d p ) x\equiv y\pmod p x≡y(modp) 。则满足：
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) vp(xn−yn)=vp(x−y)+vp(n)
② 模数为 2 2 2 时，定理内容为：
n n n 为正整数，整数 x x x 和 y y y 均为奇数。
若 n n n 为奇数，则：
v 2 ( x n − y n ) = v 2 ( x − y ) v_2(x^n-y^n)=v_2(x-y) v2(xn−yn)=v2(x−y)
若 n n n 为偶数，则：
v 2 ( x n − y n ) = v 2 ( x − y ) + v 2 ( x + y ) + v 2 ( n ) − 1 v_2(x^n-y^n)=v_2(x-y)+v_2(x+y)+v_2(n)-1 v2(xn−yn)=v2(x−y)+v2(x+y)+v2(n)−1
二、证明
模数为奇质数
引理 1 1 1 ：当 p p p 为奇质数， x , y ∈ Z + x,y\in \mathbb{Z_+} x,y∈Z+ 满足 p ∤ x , p ∤ y p\nmid x,p\nmid y p∤x,p∤y 且 x ≡ y ( m o d p ) x\equiv y\pmod p x≡y(modp) 时， v p ( x p − y p ) = v p ( x − y ) + 1 v_p{(x^p-y^p)}=v_p{(x-y)}+1 vp(xp−yp)=vp(x−y)+1 。
对两边取 v p v_p vp 得
v p ( x p − y p ) = v p ( x − y ) + v p ( x p − 1 + x p − 2 y + ⋯ + y p − 1 ) v_p(x^p-y^p)=v_p(x-y)+v_p(x^{p-1}+x^{p-2}y+\dots+y^{p-1}) vp(xp−yp)=vp(x−y)+vp(xp−1+xp−2y+⋯+yp−1)
要证 v p ( x p − y p ) = v p ( x − y ) + 1 v_p{(x^p-y^p)}=v_p{(x-y)}+1 vp(xp−yp)=vp(x−y)+1 只需证 v p ( x p − 1 + x p − 2 y + ⋯ + y p − 1 ) = 1 v_p(x^{p-1}+x^{p-2}y+\dots+y^{p-1})=1 vp(xp−1+xp−2y+⋯+yp−1)=1 即可，即证明 p ∣ ( x p − 1 + x p − 2 y + ⋯ + y p − 1 ) p \mid (x^{p-1}+x^{p-2}y+\dots+y^{p-1}) p∣(xp−1+xp−2y+⋯+yp−1) 且 p 2 ∤ x p − 1 + x p − 2 y + ⋯ + y p − 1 p^2 \nmid x^{p-1}+x^{p-2}y+\dots+y^{p-1} p2∤xp−1+xp−2y+⋯+yp−1 。
① p ∣ ( x p − 1 + x p − 2 y + ⋯ + y p − 1 ) p \mid (x^{p-1}+x^{p-2}y+\dots+y^{p-1}) p∣(xp−1+xp−2y+⋯+yp−1)
由于 x ≡ y ( m o d p ) x\equiv y\pmod p x≡y(modp) ，因此 x k ≡ y k ( m o d p ) , k ∈ Z + x^k\equiv y^k\pmod p,k\in \mathbb{Z_+} xk≡yk(modp),k∈Z+ ，所以 x p − 1 ≡ x p − 2 y ≡ ⋯ ≡ y p − 1 ( m o d p ) x^{p-1}\equiv x^{p-2}y\equiv\dots\equiv y^{p-1}\pmod p xp−1≡xp−2y≡⋯≡yp−1(modp) ，原式可化简为
x p − 1 + x p − 2 y + ⋯ + y p − 1 ≡ p x p − 1 ≡ 0 ( m o d p ) x^{p-1}+x^{p-2}y+\dots+y^{p-1}\equiv px^{p-1}\equiv0\pmod p xp−1+xp−2y+⋯+yp−1≡pxp−1≡0(modp)
故 p ∣ ( x p − 1 + x p − 2 y + ⋯ + y p − 1 ) p\mid (x^{p-1}+x^{p-2}y+\dots+y^{p-1}) p∣(xp−1+xp−2y+⋯+yp−1) 。
② p 2 ∤ ( x p − 1 + x p − 2 y + ⋯ + y p − 1 ) p^2 \nmid (x^{p-1}+x^{p-2}y+\dots+y^{p-1}) p2∤(xp−1+xp−2y+⋯+yp−1)
由于 x ≡ y ( m o d p ) x\equiv y\pmod p x≡y(modp) 不妨设 y = x + k p , k ∈ Z y=x+kp,k\in\mathbb{Z} y=x+kp,k∈Z 。
对于 t ∈ { 0 , 1 , 2 , 3 , … , p − 1 } t\in\{0,1,2,3,\dots ,p-1\} t∈{
0,1,2,3,…,p−1} ，写出右边的通项并使用二项式定理展开得到
x p − 1 − t y t = x p − 1 − t ( x + k p ) t = x p − 1 − t ( x t + C t 1 x t − 1 ( k p ) + C t 2 ( k p ) 2 + … ) x^{p-1-t}y^{t} = x^{p-1-t}(x+kp)^t=x^{p-1-t}(x^t+C_{t}^1x^{t-1}(kp)+C_t^2(kp)^2+\dots) xp−1−tyt=xp−1−t(x+kp)t=xp−1−t(xt+Ct1xt−1(kp)+Ct2(kp)2+…)
在模 p 2 p^2 p2 同余系下有
x p − 1 − t ( x t + C t 1 x t − 1 ( k p ) + C t 2 ( k p ) 2 + … ) ≡ x p − 1 − t ( x t + t x t − 1 ( k p ) + t ( t − 1 ) 2 x t − 2 ( k p ) 2 + … ) ≡ x p − 1 − t ( x t + t x t − 1 ( k p ) ) ≡ x p − 1 + t x p − 2 k p ( m o d p 2 ) \begin{aligned} x^{p-1-t}(x^t+C_{t}^1x^{t-1}(kp)+C_t^2(kp)^2+\dots) &\equiv x^{p-1-t}(x^t+tx^{t-1}(kp)+\frac{t(t-1)}{2}x^{t-2}(kp)^2+\dots) \\ &\equiv x^{p-1-t}(x^t+tx^{t-1}(kp)) \\ &\equiv x^{p-1}+tx^{p-2}kp\pmod {p^2} \end{aligned} xp−1−t(xt+Ct1xt−1(kp)+Ct2(kp)2+…)≡xp−1−t(xt+txt−1(kp)+2t(t−1)xt−2(kp)2+…)≡xp−1−t(xt+txt−1(kp))≡xp−1+txp−2kp(modp2)
据此通项原式在模 p 2 p^2 p2 剩余系下可化简为（这里化简的最后一步只有 p − 1 2 \frac{p-1}{2} 2p−1 是整数才可以，也就是 p p p 需要为奇质数）
x p − 1 + x p − 2 y + ⋯ + y p − 1 ≡ ∑ t = 0 p − 1 ( x p − 1 + t x p − 2 k p ) ≡ p x p − 1 + ( ∑ t = 1 p − 1 t ) x p − 2 k p ≡ p x p − 1 + p ( p − 1 ) 2 x p − 2 k p ≡ p x p − 1 ( m o d p 2 ) \begin{aligned} x^{p-1}+x^{p-2}y+\dots+y^{p-1}& \equiv \sum_{t=0}^{p-1}(x^{p-1}+tx^{p-2}kp) \\ &\equiv px^{p-1}+\Big(\sum_{t=1}^{p-1}t\Big) x^{p-2}kp \\ &\equiv px^{p-1}+\frac{p(p-1)}{2}x^{p-2}kp \\ &\equiv px^{p-1} \pmod {p^2} \end{aligned} xp−1+xp−2y+⋯+yp−1≡t=0∑p−1(xp−1+txp−2kp)≡pxp−1+(t=1∑p−1t)xp−2kp≡pxp−1+2p(p−1)xp−2kp≡pxp−1(modp2)
由于 x ≢ 0 ( m o d p ) x\not\equiv 0\pmod p x≡0(modp) ，因此 x p − 1 ≢ 0 ( m o d p ) x^{p-1}\not\equiv 0\pmod p xp−1≡0(modp) ，所以 p x p − 1 ≢ 0 ( m o d p 2 ) px^{p-1}\not\equiv0\pmod {p^2} pxp−1≡0(modp2) 。
接下来采用归纳方式证明模数为奇质数的情况：
证明：
不妨设 v p ( n ) = α , n = p α m v_p(n)=\alpha,n=p^\alpha m vp(n)=α,n=pαm 。
易知
x n − y n = x p α m − y p α m = ( x p α ) m − ( y p α ) m = ( x p α − y p α ) ( x m − 1 + x m − 2 y + ⋯ + y m − 1 ) \begin{aligned} x^n-y^n &= x^{p^\alpha m}-y^{p^\alpha m} = \big(x^{p^\alpha }\big)^m – \big(y^{p^\alpha }\big)^m \\ &=\big(x^{p^\alpha} – y^{p^\alpha}\big)(x^{m-1}+x^{m-2}y+\dots+y^{m-1}) \end{aligned} xn−yn=xpαm−ypαm=(xpα)m−(ypα)m=(xpα−ypα)(xm−1+xm−2y+⋯+ym−1)
由引理 1 1 1 的证明过程有 x m − 1 ≡ x m − 2 y ≡ ⋯ ≡ y m − 1 ( m o d p ) x^{m-1}\equiv x^{m-2}y\equiv \dots\equiv y^{m-1}\pmod p xm−1≡xm−2y≡⋯≡ym−1(modp) 。
则上式中右边括号可化简为
x m − 1 + x m − 2 y + ⋯ + y m − 1 ≡ m x m − 1 ( m o d p ) x^{m-1}+x^{m-2}y+\dots+y^{m-1}\equiv mx^{m-1} \pmod p xm−1+xm−2y+⋯+ym−1≡mxm−1(modp)
根据 v p ( n ) v_p(n) vp(n) 的定义可知 p α + 1 ∤ n p^{\alpha + 1}\nmid n pα+1∤n ，故 p ∤ m p\nmid m p∤m ，又 x ≢ 0 ( m o d p ) x\not\equiv0\pmod p x≡0(modp) ，因此 x m − 1 ≢ 0 ( m o d p ) x^{m-1}\not\equiv0\pmod p xm−1≡0(modp) ，所以 m x m − 1 ≢ 0 ( m o d p ) mx^{m-1}\not\equiv0\pmod p mxm−1≡0(modp) 。
因此
v p ( x n − y n ) = v p ( x p α − y p α ) + v p ( x m − 1 + x m − 2 y + ⋯ + y m − 1 ) = v p ( x p α − y p α ) v_p(x^n-y^n)=v_p(x^{p^{\alpha}}-y^{p^{\alpha}}) + v_p(x^{m-1}+x^{m-2}y+\dots+y^{m-1})=v_p(x^{p^\alpha}-y^{p^\alpha}) vp(xn−yn)=vp(xpα−ypα)+vp(xm−1+xm−2y+⋯+ym−1)=vp(xpα−ypα)
根据引理 1 1 1 开始归纳
v p ( x n − y n ) = v p ( x p α − y p α ) = v p ( ( x p α − 1 ) p − ( y p α − 1 ) p ) = v p ( x p α − 1 − y p α − 1 ) + 1 = … = v p ( x − y ) + α = v p ( x − y ) + v p ( n ) \begin{aligned} v_p(x^n-y^n)&=v_p\Big(x^{p^\alpha}-y^{p^\alpha}\Big) \\ &=v_p\Big((x^{p^{\alpha – 1}})^p – (y^{p^{\alpha – 1}})^p\Big) \\ &=v_p\Big(x^{p^{\alpha-1}}-y^{p^{\alpha – 1}}\Big) + 1 \\ &= \dots \\ &=v_p(x – y) + \alpha \\ &=v_p(x – y) + v_p(n) \end{aligned} vp(xn−yn)=vp(xpα−ypα)=vp((xpα−1)p−(ypα−1)p)=vp(xpα−1−ypα−1)+1=…=vp(x−y)+α=vp(x−y)+vp(n)
模数为 2 2 2
引理 2 2 2 ：当 n ∈ Z + n\in \mathbb{Z_+} n∈Z+ ， x , y x,y x,y 为奇整数且满足 4 ∣ ( x − y ) 4\mid (x-y) 4∣(x−y) 时， v 2 ( x n − y n ) = v 2 ( x − y ) + n v_2(x^n-y^n)=v_2(x-y)+n v2(xn−yn)=v2(x−y)+n 。
证明：
n n n 为奇数时显然。
n n n 为偶数时，不妨设 v 2 ( n ) = α , n = 2 α m v_2(n)=\alpha,n=2^\alpha m v2(n)=α,n=2αm 。根据证明奇质数的情况时得到的结论，有
v 2 ( x n − y n ) = v 2 ( x 2 α m − y 2 α m ) = v 2 ( x 2 α − y 2 α ) v_2(x^n-y^n)=v_2\Big(x^{2^\alpha m} – y^{2^\alpha m}\Big) = v_2\Big(x^{2^{\alpha}} – y^{2^{\alpha}}\Big) v2(xn−yn)=v2(x2αm−y2αm)=v2(x2α−y2α)
根据平方差公式 x 2 α − y 2 α = ( x 2 α − 1 + y 2 α − 1 ) ( x 2 α − 1 − y 2 α − 1 ) x^{2^{\alpha}} – y^{2^{\alpha}} = \Big(x^{2^{\alpha – 1}}+y^{2^{\alpha – 1}}\Big)\Big(x^{2^{\alpha – 1}} – y^{2^{\alpha -1}}\Big) x2α−y2α=(x2α−1+y2α−1)(x2α−1−y2α−1) 不断展开得
x 2 α − y 2 α = ( x 2 α − 1 + y 2 α − 1 ) ( x 2 α − 2 + y 2 α − 2 ) … ( x + y ) ( x − y ) x^{2^{\alpha}} – y^{2^{\alpha}} = \Big(x^{2^{\alpha – 1}}+y^{2^{\alpha – 1}}\Big)\Big(x^{2^{\alpha – 2}}+y^{2^{\alpha – 2}}\Big)\dots(x+y)(x-y) x2α−y2α=(x2α−1+y2α−1)(x2α−2+y2α−2)…(x+y)(x−y)
因为 x , y x,y x,y 都是奇整数，所以 x ≡ ± 1 ( m o d 4 ) x\equiv \pm1\pmod 4 x≡±1(mod4) 且 y ≡ ± 1 ( m o d 4 ) y\equiv \pm 1\pmod 4 y≡±1(mod4) ，分别两边平方得 x 2 ≡ y 2 ≡ 1 ( m o d 4 ) x^2\equiv y^2\equiv1\pmod 4 x2≡y2≡1(mod4) ，不断平方可推广至 x 2 k ≡ y 2 k ≡ 1 ( m o d 4 ) , k ∈ Z + x^{2^k}\equiv y^{2^k}\equiv1\pmod 4,k\in\mathbb{Z_+} x2k≡y2k≡1(mod4),k∈Z+ ，因此 x 2 k + y 2 k ≡ 2 ( m o d 4 ) x^{2^{k}}+y^{2^{k}}\equiv 2\pmod 4 x2k+y2k≡2(mod4) ，故 v 2 ( x 2 k + y 2 k ) = 1 v_2\Big(x^{2^{k}}+y^{2^{k}}\Big)=1 v2(x2k+y2k)=1 。据此可继续化简得
v 2 ( x 2 α − y 2 α ) = 1 × ( α − 1 ) + v 2 ( x + y ) + v 2 ( x − y ) = v 2 ( x + y ) + v 2 ( x − y ) + α − 1 v_2\Big(x^{2^{\alpha}} – y^{2^{\alpha}}\Big)=1\times(\alpha-1)+v_2(x+y)+v_2(x-y)=v_2(x+y)+v_2(x-y)+\alpha-1 v2(x2α−y2α)=1×(α−1)+v2(x+y)+v2(x−y)=v2(x+y)+v2(x−y)+α−1
又 4 ∣ x − y 4\mid x-y 4∣x−y ，因此 x ≡ y ≡ 1 ( m o d 4 ) x\equiv y\equiv 1\pmod 4 x≡y≡1(mod4) 或者 x ≡ y ≡ 3 ( m o d 4 ) x\equiv y\equiv 3\pmod 4 x≡y≡3(mod4) ，无论如何，有 x + y ≡ 2 ( m o d 4 ) x+y\equiv 2\pmod 4 x+y≡2(mod4) ，故 v 2 ( x + y ) = 1 v_2(x+y)=1 v2(x+y)=1 。因此
v 2 ( x 2 α − y 2 α ) = 1 + v 2 ( x − y ) + α − 1 = v 2 ( x − y ) + α = v 2 ( x − y ) + v 2 ( n ) v_2\Big(x^{2^{\alpha}} – y^{2^{\alpha}}\Big)=1+v_2(x-y)+\alpha – 1=v_2(x-y)+\alpha=v_2(x-y)+v_2(n) v2(x2α−y2α)=1+v2(x−y)+α−1=v2(x−y)+α=v2(x−y)+v2(n)
接下来根据引理 2 2 2 证明模数为 2 2 2 的情况：
当 n n n 为奇数时显然。
当 n n n 为偶数时，不妨设 v 2 ( n ) = α , n = 2 α m v_2(n)=\alpha,n=2^\alpha m v2(n)=α,n=2αm 。根据证明奇质数的情况时得到的结论，有
v 2 ( x n − y n ) = v 2 ( x 2 α m − y 2 α m ) = v 2 ( x 2 α − y 2 α ) = v 2 ( ( x 2 ) 2 α − 1 − ( y 2 ) 2 α − 1 ) v_2(x^n-y^n)=v_2\Big(x^{2^\alpha m} – y^{2^\alpha m}\Big) = v_2\Big(x^{2^{\alpha}} – y^{2^{\alpha}}\Big)=v_2\Big((x^2)^{2^{\alpha – 1}}-(y^2)^{2^{\alpha – 1}}\Big) v2(xn−yn)=v2(x2αm−y2αm)=v2(x2α−y2α)=v2((x2)2α−1−(y2)2α−1)
因为 x , y x,y x,y 都是奇整数，所以 x ≡ ± 1 ( m o d 4 ) x\equiv \pm1\pmod 4 x≡±1(mod4) 且 y ≡ ± 1 ( m o d 4 ) y\equiv \pm 1\pmod 4 y≡±1(mod4) ，分别两边平方得 x 2 ≡ y 2 ≡ 1 ( m o d 4 ) x^2\equiv y^2\equiv1\pmod 4 x2≡y2≡1(mod4) ，根据引理 2 2 2 得
v 2 ( ( x 2 ) 2 α − 1 − ( y 2 ) 2 α − 1 ) = v 2 ( x 2 − y 2 ) + α − 1 = v 2 ( x + y ) + v 2 ( x − y ) + v 2 ( n ) − 1 \begin{aligned} v_2\Big((x^2)^{2^{\alpha – 1}}-(y^2)^{2^{\alpha – 1}}\Big)&=v_2(x^2-y^2)+\alpha – 1 \\ &=v_2(x+y) + v_2(x-y)+v_2(n) – 1 \end{aligned} v2((x2)2α−1−(y2)2α−1)=v2(x2−y2)+α−1=v2(x+y)+v2(x−y)+v2(n)−1
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/136125.html
