LTE (Lifting The Exponent Lemma)引理是一个解指数型不定方程的强力工具。它在Olympiad folklore非常知名，虽然它的起源已经无从查找了。它和Hensel’s lemma关系密切，无论命题还是证明。本文证明它并给出它的一些应用。

我们可以用本引理解决大量的指数型不定方程问题。尤其是我们可以找到某些质因子的时候。有时LTE引理甚至能秒杀一道题。这个引理告诉我们如何求一个奇素数p在a^n-b^n中的次数。这个引理的证明是完全初等的而且对一般竞赛生不难理解。

我们记v[p](n)为p在n中的次数，。

或者说如果v[p](n)=a则p^a|n但把a换成更大的就不行。如果n不是p的倍数，v[p](n)=0

容易知道v[p](ab)=v[p](a)+v[p](b)以及v[p](a+b)≥min{v[p](a),v[p](b)}

先证明两个小引理（这两个引理中p都是奇素数）

1.如果p|x-y，(p,n)=1，(p,x)=1，那么

v[p](x^n-y^n)=v[p](x-y)

由于x^n-y^n=(x-y)(x^(n-1)+x^(n-2)y+…+y^(n-1))

而在mod p意义下，由于x=y，有

x^(n-1)+x^(n-2)y+…+y^(n-1)=n*x^(n-1)≠0

（每个加项相同，共n项）

因此v[p](x^(n-1)+x^(n-2)y+…+y^(n-1))=0

因此v[p](x^n-y^n)=v[p](x-y)+v[p](x^(n-1)+x^(n-2)y+…+y^(n-1))=v[p](x-y)

2.如果p|x-y，(p,x)=1，那么

v[p](x^p-y^p)=v[p](x-y)+1

假设x=y+k*p^a，其中(k,p)=1，则a=v[p](x-y)

由二项式定理（这里的C(m,n)表示组合数），

x^p-y^p=(x+k*p^a)^p-x^p

=(x^p+p*x^(p-1)*k*p^a+C(p,2)*x^(p-2)*k^2*p^(2a)+C(p,3)*x^(p-3)*k^2*p^(3a)+…)-x^p

=p^(a+1)*x^(p-1)*k+S

容易验证S的每一项都是p^(2a+1)的倍数

所以这个数是p^(a+1)的倍数但不是p^(a+2)的倍数（S是但p^(a+1)*x^(p-1)*k不是）

故v[p](x^p-y^p)=a+1=v[p](x-y)+1

好了，下面献上LTE引理：

如果p是奇素数，p|x-y，(p,x)=1，那么

v[p](x^n-y^n)=v[p](x-y)+v[p](n)

不断把n中的因子p搬到外面变成+1，搬完了就证完了。。。

对于n是奇数，我们还有

v[p](x^n+y^n)=v[p](x+y)+v[p](n)

这是通过把y理解成-y得到的

p=2的情况没啥用处，就不搬运了。。。

应用

1.求所有正整数n使得存在正整数x,y,k满足(x,y)=1,k>1使得3^n=x^k+y^k

解答

如果k是偶数，由于x^k和y^k mod 3都是1或0，所以都是0，这与(x,y)=1矛盾

如果k是奇数，则v[3](x^k+y^k)=v[3](k)+v[3](x+y)=v[3](k(x+y))

因此x^k+y^k≤k(x+y)（左边完全是3的幂次，右边还可能有别的），

x^(k-1)-x^(k-2)y+…+y^(k-1)≤k……(1)

显然x≠y，不妨设x>y，则

x^(k-1)-x^(k-2)*y=x^(k-2)(x-y)≥x≥2

x^(k-3)-x^(k-4)*y=x^(k-4)(x-y)≥x≥2

总之就是把(1)的前k-1项两两配对，每一对的和都不小于2

又y^(k-1)≥1,全加起来就至少是项数k

而且如果x≥3或者k>3，等号就取不到

因此x=2,y=1,k=3验证知此时n=2

2.已知p是一个奇素数，正整数x,y,m>1，证明：如果(x^p+y^p)/2=((x+y)/2)^m，则m=p

解答

由幂平均不等式m≥p

假设(x,y)=d,x=du,y=dv

则(u^p+v^p)/2=d^(m-p)*((u+v)/2)^m

任取u+v的素因子q

如果q为奇数

则v[p]((u^q+v^q)/2)=v[q](u+v)+v[q](p)≤v[q](u+v)+1≤2v[q](u+v)

而m≥p≥3，有

v[q](d^(m-p)*((u+v)/2)^m)≥v[q](((u+v)/2)^m)=m*v[q](u+v)

矛盾！

如果q只能为2，u+v就是2的幂次，假设u+v=2^a

由于(u,v)=1，u,v均为奇数

又u^(p-1)-u^(p-2)v+…+v^(p-1)共p项，为奇数

有v[2]((u^p+v^p)/2)=v[2]((u+v)/2)=a-1

又v[2](d^(m-p)*((u+v)/2)^m)≥v[2]((u+v)/2)^m)=m(a-1)

因此a=1，u=v=1，这说明x=y，进而m=p

3.求x^2009+y^2009=7^z的全部正整数解

解答

由费马小定理7|(x^2009+y^2009)-(x+y)，故7|(x+y)

故v[7](x^2009+y^2009)=v[7](2009)+v[7](x+y)=v[7](49(x+y))

因此x^2009+y^2009=7^v[7](x^2009+y^2009)=7^v[7](49(x+y))≤49(x+y)

（显然p^v[p](x)≤x）

而不等式x^2009+y^2009≤49(x+y)在x,y不全等于1时显然不成立

而且x=y=1也不成立

因此，无解

4.求所有正整数a使得对所有正整数n，4(a^n+1)是完全立方数

解答

a=1显然可以

若a>1，则a为奇数（偶立方数都是8的倍数）

所以a^2+1是4k+2型数，有一个奇素因数p

假设v[p](a^2+1)=3k

那么v[p](4(a^(2p)+1))=3k+1

这不可能（由于立方数对所有素数的次数都是3的倍数）

话说此题还有一个很神奇的做法：

如果a>1，(4(a^9+1))/(4(a^3+1))=a^6-a^3+1可以被夹在两个相邻立方数之间……

练习题

1.求所有正整数a,b>1使得a^b|b^a-1

2.求(n-1)!+1=n^m的正整数解(n,m)

3.是否存在正整数n使得n|2^n+1且n有恰好10086个素因数

4.实数a,b满足若对所有正整数n，a^n-b^n是整数，证明a,b都是整数

5.正整数a>b>1和n满足b是奇数和a^n|b^n-1，证明：a^b>3^n/n

6.求所有正整数n，使得n^2|2^n+1

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