指数提升定理

1、Summary(概述)

指数提升定理（Lifting the exponent lemma）是解决若干形如 nthn^{th} 的和差中某素因子的最大指数问题的有力工具

这里有几个可以使用该定理解决的例题：

（1）设 nn 是一个无平方因子整数，证明：不存在一对互质的 (x,y)(x,y) 满足 (x+y)3∣(xn+yn)(x+y)^3|(x^n+y^n)

（2）证明：对于任意的正整数 kk，22 是模 3k3^k 意义下的一个原根

（3）找到方程 3n=xk+yk3^n=x^k+y^k 的所有正整数解 (x,y)(x,y)，且 gcd(x,y)=1gcd(x,y)=1，保证 k⩾2k\geqslant 2

（4）设 a,ba,b 是正实数且 a−b,a2−b2,a3−b3,...a-b,a^2-b^2,a^3-b^3,... 都是正整数，证明：a,ba,b 都是正整数

2、Lifting The Exponent Theorem(指数提升定理)

首先我们定义 vp(n)v_p(n) 表示 nn 中素因子 pp 的指数，形式化的，

vp(n)=k⇔pk∣n,pk+1∤nv_p(n)=k\Leftrightarrow p^k|n,p^{k+1}\nmid n

Lifting The Exponent Theorem(指数提升定理)
设 pp 为素数，x,y,n∈Zx,y,n\in Z，n>0n>0，满足 p∣(x−y)p|(x-y)，且 p∤x,p∤yp\nmid x,p\nmid y
（1）若 pp 为奇数，则 vp(xn−yn)=vp(x−y)+vp(n)v_p(x^n-y^n)=v_p(x-y)+v_p(n)
（2）若 p=2p=2 且 nn 为偶数，则 v2(xn−yn)=v2(x−y)+v2(n)+v2(x+y)−1v_2(x^n-y^n)=v_2(x-y)+v_2(n)+v_2(x+y)-1

注意到 (1)(1)中把 yy 换成 −y-y 可以得到：

vp(xn+yn)=vp(x+y)+vp(n)v_p(x^n+y^n)=v_p(x+y)+v_p(n)

例：求 518−2185^{18}-2^{18} 的结果中因子 33 的指数

由指数提升定理，

v3(518−218)=v3(5−2)+v3(18)=1+2=3v_3(5^{18}-2^{18})=v_3(5-2)+v_3(18)=1+2=3

3、Proof of the Theorem(定理证明)

我们先证明定理的 (1)(1)，(2)(2) 的证明是类似的，设 p∣(x−y)p|(x-y) 且 p∤x,p∤yp\nmid x,p\nmid y

Lemma 1
若 pp 不是 nn 的约数，则
vp(xn−yn)=vp(x−y)v_p(x^n-y^n)=v_p(x-y)

证明：由 nn 次方差公式可得

xn−ynx−y=xn−1+xn−2y+⋯+yn−1\frac{x^n-y^n}{x-y}=x^{n-1}+x^{n-2}y+\cdots+y^{n-1}

由于 p∣(x−y)p|(x-y) 且 pp 不是 x,yx,y 的约数，故 x≡y( mod p)x\equiv y(\bmod p)，因此

xn−ynx−y≡nxn−1( mod p)\frac{x^n-y^n}{x-y}\equiv nx^{n-1}(\bmod p)

由于 p∤n,p∤xp\nmid n,p\nmid x，所以 pp 不是 xn−ynx−y\frac{x^n-y^n}{x-y} 的约数，因此

vp(xn−yn)=vp(x−y)v_p(x^n-y^n)=v_p(x-y)

注：nn 次方差公式：

an−bn=(a−b)(an−1+an−2b+an−3b2+⋯+abn−2+bn−1)a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+\cdots+ab^{n-2}+b^{n-1})

若 nn 是奇数，有 nn 次方和公式：

an+bn=(a+b)(an−1−an−2b+an−3b2+⋯−abn−2+bn−1)a^n+b^n=(a+b)(a^{n-1}-a^{n-2}b+a^{n-3}b^2+\cdots-ab^{n-2}+b^{n-1})

Lemma 2
当 n=pn=p 时指数提升定理定理成立，即
vp(xp−yp)=vp(x−y)+1v_p(x^p-y^p)=v_p(x-y)+1

证明：由 nn 次方差公式得到

xp−yp=(x−y)(xp−1+xp−2y+⋯+yp−1)x^p-y^p=(x-y)(x^{p-1}+x^{p-2}y+\cdots+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)+v_p(x^{p-1}+x^{p-2}y+\cdots+y^{p-1})

所以只需要证明

vp(xp−1+xp−2y+⋯+yp−1)=1v_p(x^{p-1}+x^{p-2}y+\cdots+y^{p-1})=1

即可，不妨设 y=x+kpy=x+kp，则

xp−1+xp−2y+⋯+yp−1≡xp−1+(xp−1+pkxp−2)+(xp−1+2pkxp−2)+⋯+(xp−1+(p−1)pkxp−2)≡pxp−1+p(p−1)2pkxp−2≡pxp−1( mod p2)\begin{aligned}x^{p-1}+x^{p-2}y+\cdots+y^{p-1}&\equiv x^{p-1}+(x^{p-1}+pkx^{p-2})+(x^{p-1}+2pkx^{p-2})+\cdots+(x^{p-1}+(p-1)pkx^{p-2})\\ &\equiv px^{p-1}+\frac{p(p-1)}{2}pkx^{p-2} \\&\equiv px^{p-1}(\bmod p^2)\end{aligned}

故 xp−1+xp−2y+⋯+yp−1x^{p-1}+x^{p-2}y+\cdots+y^{p-1} 能被 pp 整除，而不能被 p2p^2 整除

故 vp(xp−1+xp−2y+⋯+yp−1)=1v_p(x^{p-1}+x^{p-2}y+\cdots+y^{p-1})=1

指数提升定理（1）
vp(xn−yn)=vp(x−y)+vp(n)v_p(x^n-y^n)=v_p(x-y)+v_p(n)

证明：设 n=pkan=p^k a，其中 a∤pa\nmid p，则

vp(xn−yn)=vp((xpk)a−(ypk)a)=vp(xpk−ypk)=vp((xpk−1)p−(ypk−1)p)=vp(xpk−1−ypk−1)+1=vp(x−y)+k=vp(x−y)+vp(n)\begin{aligned}v_p(x^n-y^n)&=v_p((x^{p^k})^a-(y^{p^k})^a)=v_p(x^{p^k}-y^{p^k})\\&=v_p((x^{p^{k-1}})^p-(y^{p^{k-1}})^p)\\&=v_p(x^{p^{k-1}}-y^{p^{k-1}})+1\\&=v_p(x-y)+k\\&=v_p(x-y)+v_p(n)\end{aligned}

4、Examples(例题)

Problem 1
设 nn 是一个无平方因子整数，证明：不存在一对互质的 (x,y)(x,y) 满足
(x+y)3∣(xn+yn)(x+y)^3|(x^n+y^n)

证明：假设存在一对互质的 (x,y)(x,y) 满足 (x+y)3∣(xn+yn)(x+y)^3|(x^n+y^n)

情形一：nn 是偶数

如果存在奇素数 p∣(x+y)p|(x+y)，则

xn+yn≡xn+(−x)n≡2xn( mod p)x^n+y^n\equiv x^n+(-x)^n\equiv 2x^n(\bmod p)

由于 p∣(x+y)∣(x+y)3∣(xn+yn)p|(x+y)|(x+y)^3|(x^n+y^n)，故 p∣x,p∣yp|x,p|y，x,yx,y 不互质，矛盾

故不存在奇素数 p∣(x+y)p|(x+y)，因此 (x+y)(x+y) 是22的整次幂，由于 x,yx,y 互质，所以它们都是奇数

因为 nn 是偶数，故 xn≡1( mod 8)x^n\equiv 1(\bmod 8) 且 yn≡1( mod 8)y^n\equiv 1(\bmod 8)

注：由欧拉定理得到

xn≡xn%4(mod8)x^n\equiv x^{n\%4}(mod 8)

由于 nn 是偶数，故指数只能是 00 或 22，指数为 00 显然成立

指数为 22 时，x%8x\%8 的结果只可能是 1,3,5,71,3,5,7，它们都是成立的

故 xn+yn≡2( mod 8)x^n+y^n\equiv 2(\bmod 8)，v2(xn+yn)=1v_2(x^n+y^n)=1，而 v2((x+y)3)≥3v_2((x+y)^3)\geq 3，矛盾

情形二：nn 是奇数

如果存在奇素数 p∣(x+y)p|(x+y)，则 3vp(x+y)≤vp(xn+yn)3v_p(x+y)\leq v_p(x^n+y^n)

由指数提升定理，结合 nn 是无平方因子数，

3vp(x+y)≤vp(xn+yn)=vp(x+y)≤vp(x+y)+13v_p(x+y)\leq v_p(x^n+y^n)=v_p(x+y)\leq v_p(x+y)+1

故 vp(x+y)≤12v_p(x+y)\leq \frac{1}{2}，而 p∣(x+y)p|(x+y)，矛盾

故不存在奇素数 p∣(x+y)p|(x+y)，因此 (x+y)(x+y) 是 22 的整次幂

在这种情况下，nn 是奇数，v2(n)=0v_2(n)=0，由指数提升定理 v2(xn+yn)=v2(x+y)v_2(x^n+y^n)=v_2(x+y)，而

xn+ynx+y=xn−1−xn−2y+...−xyn−2+yn−1\frac{x^n+y^n}{x+y}=x^{n-1}-x^{n-2}y+...-xy^{n-2}+y^{n-1}

注意到右边有奇数项，每项都是奇数，故

v2(xn−1−xn−2y+...−xyn−2+yn−1)=0v_2(x^{n-1}-x^{n-2}y+...-xy^{n-2}+y^{n-1})=0

而 v2(xn+ynx+y)=1v_2(\frac{x^n+y^n}{x+y})=1，矛盾

Problem 2　
证明：对于任意的正整数 kk，22 是模 3k3^k 意义下的一个原根

我们需要找到最小的 nn 满足

2n≡1( mod 3k)2^n \equiv 1(\bmod 3^k)

即 3k∣(2n−1)3^k|(2^n-1)，故 2n≡1( mod 3)2^n\equiv 1(\bmod 3)，由欧拉定理，

2n≡2n%2≡1(mod3)2^n\equiv 2^{n\%2}\equiv 1(mod 3)

故 nn 为偶数，设 n=2mn=2m，则 3k∣(4m−1)3^k|(4^m-1)，根据指数提升定理，

k≤v3(4m−1m)=v3(4−1)+v3(m)=1+v3(m)k\leq v_3(4^m-1^m)=v_3(4-1)+v_3(m)=1+v_3(m)

故 v3(m)≥k−1v_3(m)\geq k-1，所以最小的 m=3k−1m=3^{k-1}，对应的，最小的

n=2×3k−1=ϕ(3k)n=2\times 3^{k-1}=\phi(3^k)

故 22 必定是模 3k3^k 意义下的一个原根

Problem 3　
找到方程 3n=xk+yk3^n=x^k+y^k
的所有正整数解 (x,y)(x,y)，满足 gcd(x,y)=1gcd(x,y)=1，保证 k⩾2k\geqslant 2

若 x,yx,y 中有一个能整除 33，那么它们都能，这与 gcd(x,y)=1gcd(x,y)=1 矛盾，所以 x,yx,y 均不能整除 33

若 kk 是偶数，由欧拉定理，

xk≡1,yk≡1,xk+yk≡2( mod 3)x^k\equiv 1,y^k\equiv 1,x^k+y^k\equiv 2(\bmod 3)

原方程不可能成立，无解

若 kk 是奇数，若 n=0n=0，xk+yk=1x^k+y^k=1，显然无解，所以 n≥1n\geq 1 且3∣(x+y)3|(x+y)，由指数提升定理，

n=v3(xk+yk)=v3(x+y)+v3(k)n=v_3(x^k+y^k)=v_3(x+y)+v_3(k)

xk+yk=3n=3v3(x+y)3v3(k)=(x+y)kx^k+y^k=3^n=3^{v_3(x+y)}3^{v_3(k)}=(x+y)k

不失一般性地，设 x>yx>y，则

k=xn+ynx+y=xk−1−xk−2y+⋯−xyk−2+yk−1=(x−y)(xk−2+xk−4y2+⋯+xyk−3)+yk−1\begin{aligned}k&=\frac{x^n+y^n}{x+y}=x^{k-1}-x^{k-2}y+\cdots-xy^{k-2}+y^{k-1}\\&=(x-y)(x^{k-2}+x^{k-4}y^2+\cdots+xy^{k-3})+y^{k-1}\end{aligned}

由于 RHS≥xk−2RHS\geq x^{k-2}，因此 xk−2≤kx^{k-2}\leq k，故 ln⁡(x)≤ln⁡(k)k−2\ln(x)\leq \frac{\ln(k)}{k-2}，其中 k≥3,x≥2k\geq 3,x\geq 2

根据导数分析，f(k)=ln⁡(k)k−2f(k)=\frac{\ln(k)}{k-2} 在 [3,+∞)[3,+\infty) 上单调递减，故 ln⁡(x)≤ln⁡(3)\ln(x)\leq \ln(3)，x≤3x\leq 3

而 xx 不能整除 33，故 x=2,y=1x=2,y=1

这种情况下，2k−2>k2^{k-2}>k 仅在 k=3,4k=3,4 时成立，kk 是奇数，故 k=3k=3

经检验，x=2,y=1,k=3x=2,y=1,k=3 是原方程的解

故当 k=3k=3 时，方程的解为 (2,1)(2,1) 或 (1,2)(1,2)，当 k≠3k\neq3时，方程无解

Problem 4　
设 a,ba,b 是正实数且 a−b,a2−b2,a3−b3,…a-b,a^2-b^2,a^3-b^3,\ldots 都是正整数，证明：a,ba,b 都是正整数

因为 (a−b)∈Z，(a2−b2)∈Z(a-b)\in Z，(a^2-b^2)\in Z，所以 a+b=a2−b2a−b∈Qa+b=\frac{a^2-b^2}{a-b}\in Q

所以 a=12(a+b)+12(a−b)a=\frac{1}{2}(a+b)+\frac{1}{2}(a-b) 是有理数，同理 bb 也是有理数

不妨设 a=xz,b=yza=\frac{x}{z},b=\frac{y}{z}，x,y,zx,y,z 均为正整数，且 zz 尽可能小

则由已知条件，zn∣(xn−yn)z^n|(x^n-y^n) 对于所有的 nn 恒成立

设素数 p∣zp|z，由于 z∣(x−y)z|(x-y)，p∣(x−y)p|(x-y)，若 p∣x,p∣yp|x,p|y，我们可以写出

a=xpzp,b=ypzpa=\frac{\frac{x}{p}}{\frac{z}{p}},b=\frac{\frac{y}{p}}{\frac{z}{p}}

也就是说 zz 可以更小，所以 p∤x,p∤yp\nmid x,p\nmid y，这样的话我们就可以应用指数提升定理

若 pp 为奇数，则

n≤vp(zn)=vp(xn−yn)=vp(x−y)+vp(n)n\leq v_p(z^n)=v_p(x^n-y^n)=v_p(x-y)+v_p(n)

⇒pn≤(x−y)n⇒pnn≤(x−y)\Rightarrow p^n\leq (x-y)n \Rightarrow \frac{p^n}{n}\leq (x-y)

当 n→+∞n\to +\infty 时，f(n)=pnn→∞f(n)=\frac{p^n}{n}\to \infty，而 (x−y)(x-y) 是一个定值，显然不可能恒成立

若 pp 为偶数，即 p=2p=2 时

n≤v2(zn)=v2(xn−yn)=v2(x−y)+v2(n)+v2(x+y)−1n\leq v_2(z^n)=v_2(x^n-y^n)=v_2(x-y)+v_2(n)+v_2(x+y)-1

得到 2n+1n≤(x−y)(x+y)\frac{2^{n+1}}{n}\leq (x-y)(x+y)，同样不可能恒成立

故不存在素数 p∣zp|z，即 z=1z=1，所以 a,ba,b 均为正整数

5、Exercises(练习题目)

1、求方程 3x=2xy+13^x=2^xy+1 的正整数解 (x,y)(x,y) 的个数

2、求方程 px−yp=1p^x-y^p=1 的所有正整数解 (x,y,p)(x,y,p)，其中 pp 为素数

3、求所有正整数 a,b>1a,b>1，使得 ab∣(ba−1)a^b|(b^a-1)

4、求方程 (n−1)!+1=nm(n-1)!+1=n^m 的所有正整数解 (n,m)(n,m)

5、是否存在正整数 nn 使得 n∣(2n+1)n|(2^n+1)，且 nn 有 1008610086 个素因子

6、求所有正整数 nn，使得 n2∣2n+1n^2|2^n+1

7、已知 pp 是一个奇素数，正整数 x,y,m>1x,y,m>1，证明：如果 (xp+yp)2=(x+y2)m\frac{(x^p+y^p)}{2}=(\frac{x+y}{2})^m，则 m=pm=p

8、求 x2009+y2009=7zx^{2009}+y^{2009}=7^z 的所有正整数解 (x,y,z)(x,y,z)

9、求所有正整数 aa 使得对所有正整数 nn，4(an+1)4(a^n+1)是完全立方数

10、给定正整数 u>1u>1，证明：至多存在有限个三元正整数组 (n,a,b)(n,a,b) 满足 n!=ua−ubn!=u^a-u^b