LTE引理是一个解指数型不定方程的强力工具。它在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
(1)设p为奇素数，整数a,b均不能被p整除 a-b恰能被p^k整除，k为正整数 n恰能被p^m整除，m为非负整数 则a^n-b^n恰能被p^(m+k)整除
（2）设a,b为奇数，a-b恰能被2^k整除，k为大于1的正整数 n恰能被2^m整除，m为非负整数 则a^n-b^n恰能被2^(m+k)整除
秒杀题目有：
1,求所有正整数n,使得n^2整除2^n+1(31届IMO第3题)
2,求所有正整数n,p,其中p为素数，n^(p-1)整除(p-1)^n+1(40届IMO第4题)
3,已知正整数m,n,k满足3^m,3^n,3^k模10000同余，且m,n,k可以构成三角形三边长，求m+n+k最小值 4，http://tieba.http://www.35331.cn//p/1678380837中楼主的题目 5,（原创题）：求所有正整数x,y,使x^y整除y^x+1 6,(原创题）：求所有正整数x,y,使x^y整除y^x-1
7,（原创题）:求所有正整数a,使得存在无限多个正整数n,使得n^2整除a^n+1 Rules: 1) Use
for typing.
2) Use sum and product notations whenever you can in place of informal ellipses . Use proper indices, cyclic/symmetric
notation whenever applicable. 3) Number your results.
4) Name your results if possible.
5) Check previous results to prevent repetition. State special cases or generalizations.
6) Place an empty line between the end of a result and the beginning of another result if you have multiple results in a post. 7) State the domain of your results.
8) Derivations are not necessary as they are mostly intuitive, but go ahead if you want. Hide any posted derivations though.
In general try to stick to non-complex number identities because this is meant for elementary purposes. Also, minimize geometry, combinatorics, number theory, etc. results. Algebra only!
I'll start off with some common ones:
Result 1. - Difference of same powers
for non-negative integers
Result 2. - Sum of same odd powers
and all reals .
for non-negative integers
Result 3. - Special Case of Result 1. - Difference of squares
and all reals .
for all reals
Result 4. - Special Case of Result 1. - Difference of cubes
.
for all reals
Result 5. - Sum of Squares - Different representations
.
for all reals
Result 6.
.
for all reals
Result 7.
.
for all reals
Result 8.
.
for all reals
Result 9.
.
for all reals Result 10.
.
for all reals Result 11.
.
for all reals
Result 12.
.
for all reals .
If you're wondering what else to post, there are the Binomial and Multinomial Theorems for integer exponents, their numerous special smaller cases, The Sophie Germain Factorization and so many more! Have fun.
One we reach a significant number of Results, I will put them into a PDF (with credits given to the respective posters of course) and post it here and in the Olympiad Articles forum.
Note to everyone: If you got a Result specifically from a source like a book, file, person, etc, please give your source credit. P.S. This is not a thread to collect nice or classical or useful inequalities. This is only for algebraic manipulations, factorizations and such. Result 13.
for all reals
Result 14.
for all reals
Result 15.
for all reals
Result 16.
for all reals Result 17.
f
or all reals Result 18.
for all
reals Result 19.
for all reals
Result 20.
for all reals
Result 21.
for all reals
Result 22.
for
all reals Result 23.
for all reals Result 24.
for all
reals
Last edited by 123steeve on Jul 07, 2011, 9:51 am, edited 3 times in total. Method of Lagrange for root within another root: Let this be Result 24,5
Source: Algebra class
95% of professing Pastafarian teens won't stand up for The Flying Spaghetti Monster. If you are one of the 5% who will, please copy and paste this into your signature.
Last edited by Markomak1 on Jun 09, 2011, 8:01 pm, edited 2 times in total.
Result 25
for all