Link Search Menu Expand Document

Lifting The Exponent Lemma
(LTE)

Amir Hossein Parvardi

Version 6
February 20, 2021

Lifting The Exponent Lemma is a powerful method for solving exponential Diophantine equations. It is pretty well-known in the Olympiad folklore (see, e.g., Reference 3) though its origins are hard to trace. Mathematically, it is a close relative of the classical Hensel’s lemma (see Reference 2) in number theory (in both the statement and the idea of the proof). In this article we analyze this method and present some of its applications.

We can use the Lifting The Exponent Lemma (this is a long name, let’s call it LTE!) in lots of problems involving exponential equations, especially when we have some prime numbers (and actually in some cases it “explodes” the problems). This lemma shows how to find the greatest power of a prime p —which is often 3— that divides an+bn for some positive integers a and b. The proofs of theorems and lemmas in this article have nothing difficult and all of them use elementary mathematics. Understanding the theorem’s usage and its meaning is more important to you than remembering its detailed proof.

I have to thank Fedja, darij grinberg (Darij Grinberg), makar and ZetaX (Daniel) for their notifications about the article. And I specially appreciate JBL (Joel) and Fedja helps about TEX issues.

Definitions and Notation

For two integers a and b we say a is divisible by b and write b|a if and only if there exists some integer q such that a=qb.

We define vp(x) to be the greatest power in which a prime p divides x; in particular, if vp(x)=α then pα|x but pα+1x. We also write pαx, if and only if vp(x)=α. So we have vp(xy)=vp(x)+vp(y) and vp(x+y) min{vp(x),vp(y)}.

Example

The greatest power of 3 that divides 63 is 32, because 32=9|63 but 33=2763. In particular, 3263 or v3(63)=2.

Example

Clearly we see that if p and q are two different prime numbers, then vp(pαqβ)=α, or pαpαqβ.

Note: We have vp(0)= for all primes p.

Two Important and Useful Lemmas

Lemma 1

Let x and y be (not necessary positive) integers and let n be a positive integer. Given an arbitrary prime p (in particular, we can have p=2) such that gcd(n,p)=1, p|xy and neither x, nor y is divisible by p (i.e., px and py). We have

vp(xnyn)=vp(xy).

Proof

We use the fact that

xnyn=(xy)(xn1+xn2y+xn3y2++yn1).

Now if we show that pxn1+xn2y+ xn3y2++yn1, then we are done.

In order to show this, we use the assumption p|xy. So we have xy0modp, or xymodp. Thus

xn1+xn2y+xn3y2++yn1xn1+xn2x+xn3x2++xxn2+xn1nxn10modp.

This completes the proof.

Lemma 2

Let x and y be (not necessary positive) integers and let n be an odd positive integer. Given an arbitrary prime p (in particular, we can have p=2) such that gcd(n,p)=1, p|x+y and neither x, nor y is divisible by p, we have

vp(xn+yn)=vp(x+y).

Proof

Since x and y can be negative, using Lemma 1 we obtain

vp(xn(y)n)=vp(x(y))vp(xn+yn)=vp(x+y).

Note that since n is an odd positive integer we can replace (y)n with yn.

Lifting The Exponent Lemma (LTE)

Theorem 1 First Form of LTE

Let x and y be (not necessary positive) integers, let n be a positive integer, and let p be an odd prime such that p|xy and none of x and y is divisible by p (i.e., px and py). We have

vp(xnyn)=vp(xy)+vp(n).

Proof

We may use induction on vp(n). First, let us prove the following statement:

(1)vp(xpyp)=vp(xy)+1.

In order to prove this, we will show that

(2)p|xp1+xp2y++xyp2+yp1

and

(3)p2xp1+xp2y++xyp2+yp1.

For (2), we note that

xp1+xp2y++xyp2+yp1pxp10modp.

Now, let y=x+kp, where k is an integer. For an integer 1t<p we have

ytxp1t(x+kp)txp1txp1t(xt+t(kp)(xt1)+t(t1)2(kp)2(xt2)+)xp1t(xt+t(kp)(xt1))xp1+tkpxp2modp2

This means

ytxp1txp1+tkpxp2modp2,t=1,2,3,4,,p1.

Using this fact, we have

xp1+xp2y++xyp2+yp1xp1+(xp1+kpxp2)+(xp1+2kpxp2)++(xp1+(p1)kpxp2)pxp1+(1+2++p1)kpxp2pxp1+p(p1)2kpxp2pxp1+p12kp2xp1pxp10modp2.

So we proved (3) and the proof of (1) is complete. Now let us return to our problem. We want to show that

vp(xnyn)=vp(xy)+vp(n).

Suppose that n=pαb where gcd(p,b)=1. Then

vp(xnyn)=vp((xpα)b(ypα)b)=vp(xpαypα)=vp((xpα1)p(ypα1)p)=vp(xpα1ypα1)+1=vp((xpα2)p(ypα2)p)+1=vp(xpα2ypα2)+2=vp(xp1yp1)+α1=vp(xy)+α=vp(xy)+vp(n).

Note that we used the fact that if p|xy, then we have p|xkyk, because we have xy|xkyk for all positive integers k. The proof is complete.

Theorem 2 Second Form of LTE

Let x, y be two integers, n be an odd positive integer, and p be an odd prime such that p|x+y and none of x and y is divisible by p. We have

vp(xn+yn)=vp(x+y)+vp(n).

Proof

This is obvious using Theorem 1. See the trick we used in proof of Lemma 2.

What about p=2?

Question. Why did we assume that p is an odd prime, i.e., p2? Why can’t we assume that p=2 in our proofs?

Hint. Note that p12 is an integer only for p>2.

Theorem 3 LTE for the case p=2

Let x and y be two odd integers such that 4|xy. Then

v2(xnyn)=v2(xy)+v2(n).

Proof

We showed that for any prime p such that gcd(p,n)=1, p|xy and none of x and y is divisible by p, we have

vp(xnyn)=vp(xy)

Let m be an odd integer and k be a positive integer such that n=m2k. So it suffices to show that

v2(x2ky2k)=v2(xy)+k.

Factorization gives

x2ky2k=(x2k1+y2k1)(x2k2+y2k2)(x2+y2)(x+y)(xy)

Now since xy±1mod4 then we have x2i y2i1mod4 for all positive integers i and so x2i+y2i2mod4, i=1,2,3, Also, since x and y are odd and 4|xy, we have x+y2mod4. This means the power of 2 in all of the factors in the above product (except xy) is one. We are done.

Theorem 4

Let x and y be two odd integers and let n be an even positive integer. Then

v2(xnyn)=v2(xy)+v2(x+y)+v2(n)1.

Proof

We know that the square of an odd integer is of the form 4k+1. So for odd x and y we have 4|x2y2. Now let m be an odd integer and k be a positive integer such that n=m2k. Then

v2(xnyn)=v2(xm2kym2k)=v2((x2)2k1(y2)2k1)=v2(x2y2)+k1=v2(xy)+v2(x+y)+v2(n)1.

Summary

Let p be a prime number and let x and y be two (not necessary positive) integers that are not divisible by p. Then:

a. For a positive integer n

  • if p2 and p|xy, then
vp(xnyn)=vp(xy)+vp(n).
  • if p=2 and 4|xy, then
v2(xnyn)=v2(xy)+v2(n).
  • if p=2, n is even, and 2|xy, then
v2(xnyn)=v2(xy)+v2(x+y)+v2(n)1.

b. For an odd positive integer n, if p|x+y, then

vp(xn+yn)=vp(x+y)+vp(n).

c. For a positive integer n with gcd(p,n)=1, if p|xy, we have

vp(xnyn)=vp(xy).

If n is odd, gcd(p,n)=1, and p|x+y, then we have

vp(xn+yn)=vp(x+y).

Note: The most common mistake in using LTE is when you don’t check the p|x±y condition, so always remember to check it. Otherwise your solution will be completely wrong.

Problems with solutions

Problem 1 Russia 1996

Find all positive integers n for which there exist positive integers x, y and k such that gcd(x,y)=1, k>1 and 3n=xk+yk.

Solution

k should be an odd integer (otherwise, if k is even, then xk and yk are perfect squares, and it is well known that for integers a, b we have 3|a2+b2 if and only if 3|a and 3|b, which is in contradiction with gcd(x,y)=1).

Suppose that there exists a prime p such that p|x+y. This prime should be odd. So vp(3n)=vp(xk+yk), and using Theorem 2 we have vp(3n)= vp(xk+yk)= vp(k)+vp(x+y). But p|x+y means that vp(x+y)1>0 and so vp(3n)=vp(k)+vp(x+y)>0 and so p|3n. Thus p=3. This means x+y=3m for some positive integer m. Note that n=v3(k)+m. There are two cases:

  • m>1

    We can prove by induction that 3aa+2 for all integers a1, and so we have v3(k)k2 (why?). Let M=max(x,y). Since x+y=3m9, we have M5. Then

    Mk15k1Mx+y2=123mxk+ykMk=MMk1>123m5k1≥>>3m5k2≥>>3m+k2≥>>≥3m+v3(k)=3n

    which is a contradiction.

  • m=1

    Then x+y=3, so x=1, y=2 (or x=2, y=1). Thus 31+v3(k)=1+2k. But note that 3v3(k)|k so 3v3(k)k. Thus

    1+2k=3v3(k)+1=33v3(k)3k1+2k3k

    And one can check that the only odd value of k>1 that satisfies the above inequality is k=3. So (x,y,n,k)= (1,2,2,3), (2,1,2,3) in this case.

Thus, the final answer is n=2.

Problem 2 Balkan 1993

Let p be a prime number and m>1 be a positive integer. Show that if for some positive integers x>1, y>1 we have

xp+yp2=(x+y2)m,

then m=p.

Solution

One can prove by induction on p that xp+yp2(x+y2)p for all positive integers p. Now since xp+yp2=(x+y2)m, we should have mp. Let d=gcd(x,y), so there exist positive integers x1, y1 with gcd(x1,y1)=1 such that x=dx1, y=dy1 and 2m1(x1p+y1p)=dmp(x1+y1)m. There are two cases:

  • Assume that p is odd.

    Take any prime divisor q of x1+y1 and let v=vq(x1+y1). If q is odd, we see that vq(x1p+y1p)=v+vq(p) and vq(dmp(x1+y1)m)mv (because q may also be a factor of d). Thus m2 and p2, giving an immediate contradiction. If q=2, then m1+vmv, so v1 and x1+y1=2, i.e., x=y, which immediately implies m=p.

  • Assume that p=2.

    We notice that for x+y4 we have x2+y22< 2(x+y2)2 (x+y2)3, so m=2. It remains to check that the remaining cases (x,y)=(1,2),(2,1) are impossible.

Problem 3

Find all positive integers a, b that are greater than 1 and satisfy

ba|ab1.

Solution

Let p be the least prime divisor of b. Let m be the least positive integer for which p|am1. Then m|b and m|p1, so any prime divisor of m divides b and is less than p. Thus, not to run into a contradiction, we must have m=1. Now, if p is odd, we have avp(b)vp(a1)+vp(b), so (a1) (a1)vp(b) vp(a1), which is impossible. Thus p=2, b is even, a is odd and av2(b)v2(a1)+v2(a+1)+v2(b)1 whence a (a1)v2(b)+1 v2(a1)+v2(a+1), which is possible only if a=3, v2(b)=1. Put b=2B with odd B and rewrite the condition as 23B3|32B1. Let q be the least prime divisor of B (now, surely, odd). Let n be the least positive integer such that q|3n1. Then n|2B and n|q1 whence n must be 1 or 2 (or B has a smaller prime divisor), so q|31=2 or q|321=8, which is impossible.

Thus B=1 and b=2.

Problem 4

Find all positive integer solutions of the equation x2009+y2009=7z.

Solution

Factor 2009. We have 2009=7241. Since x+y|x2009+y2009 and x+y>1, we must have 7|x+y. Removing the highest possible power of 7 from x, y (why?), we get a solution of the equation such that 7x,y. We only need to check if there exists that solution. In that case, v7(x2009+y2009)= v7(x+y)+ v7(2009)= v7(x+y)+2, so x2009+y2009= 49k(x+y) where 7k. But we have x2009+y2009=7z, which means the only prime factor of x2009+y2009 is 7, so k=1. Thus x2009+y2009= 49(x+y). But in this equation the left hand side is much larger than the right hand one if max(x,y)>1, and, clearly, (x,y)=(1,1) is not a solution. Thus the given equation does not have any solutions in the set of positive integers.

Challenge Problems

Problem 1

Let k be a positive integer. Find all positive integers n such that 3k|2n1.

Problem 2 UNESCO Competition 1995

Let a, n be two positive integers and let p be an odd prime number such that

ap1modpn

Prove that

a1modpn1

Problem 3 Iran Second Round 2008

Show that the only positive integer value of a for which 4(an+1) is a perfect cube for all positive integers n, is 1.

Problem 4

Let k>1 be an integer. Show that there exists infinitely many positive integers n such that

n|1n+2n+3n++kn.

Problem 5 Ireland 1996

Let p be a prime number, and a and n positive integers. Prove that if

2p+3p=an

then n=1.

Problem 6 Russia 1996

Let x, y, p, n, k be positive integers such that n is odd and p is an odd prime. Prove that if xn+yn=pk, then n is a power of p.

Problem 7

Find the sum of all the divisors d of N=19881 which are of the form d=2a3b with a,bN.

Problem 8

Let p be a prime number. Solve the equation ap1=pk in the set of positive integers.

Problem 9

Find all solutions of the equation

(n1)!+1=nm

in positive integers.

Problem 10 Bulgaria 1997

For some positive integer n, the number 3n2n is a perfect power of a prime. Prove that n is a prime.

Problem 11

Let m, n, b be three positive integers with mn and b>1. Show that if prime divisors of the numbers bn1 and bm1 be the same, then b+1 is a perfect power of 2.

Problem 12 IMO ShortList 1991

Find the highest degree k of 1991 for which 1991k divides the number

199019911992+199219911990.

Problem 13

Prove that the number aa11 is never square-free for all integers a>2.

Problem 14 Czech Slovakia 1996

Find all positive integers x, y such that pxyp=1, where p is a prime.

Problem 15

Let x and y be two positive rational numbers such that for infinitely many positive integers n, the number xnyn is a positive integer. Show that x and y are both positive integers.

Problem 16 IMO 2000

Does there exist a positive integer n such that n has exactly 2000 prime divisors and n divides 2n+1?

Problem 17 China Western Mathematical Olympiad 2010

Suppose that m and k are non-negative integers, and p=22m+1 is a prime number. Prove that

  • 22m+1pk1modpk+1
  • 2m+1pk is the smallest positive integer n satisfying the congruence equation 2n1modpk+1.

Problem 18

Let p5 be a prime. Find the maximum value of positive integer k such that

pk|(p2)2(p1)(p4)p1.

Problem 19

Let a, b be distinct real numbers such that the numbers

ab,a2b2,a3b3,

are all integers. Prove that a, b are both integers.

Problem 20 MOSP 2001

Find all quadruples of positive integers (x,r,p,n) such that p is a prime number, n,r>1 and xr1=pn.

Problem 21 China TST 2009

Let a>b>1 be positive integers and b be an odd number, let n be a positive integer. If bn|an1, then show that ab>3nn.

Problem 22 Romanian Junior Balkan TST 2008

Let p be a prime number, p3, and integers a, b such that p|a+b and p2|a3+b3. Prove that p2|a+b or p3|a3+b3.

Problem 23

Let m and n be positive integers. Prove that for each odd positive integer b there are infinitely many primes p such that pn1modbm implies bm1|n.

Problem 24 IMO 1990

Determine all integers n>1 such that

2n+1n2

is an integer.

Problem 25

Find all positive integers n such that

2n1+1n

is an integer.

Problem 26

Find all primes p, q such that (5p2p)(5q2q)pq is an integer.

Problem 27

For some natural number n let a be the greatest natural number for which 5n3n is divisible by 2a. Also let b be the greatest natural number such that 2bn. Prove that ab+3.

Problem 28

Determine all sets of non-negative integers x, y and z which satisfy the equation

2x+3y=z2.

Problem 29 IMO ShortList 2007

Find all surjective functions f:NN such that for every m,nN and every prime p, the number f(m+n) is divisible by p if and only if f(m)+f(n) is divisible by p.

Problem 30 Romania TST 1994

Let n be an odd positive integer. Prove that ((n1)n+1)2 divides n(n1)(n1)n+1+n.

Problem 31

Find all positive integers n such that 3n1 is divisible by 2n.

Problem 32 Romania TST 2009

Let a,n2 be two integers, which have the following property: there exists an integer k2, such that n divides (a1)k. Prove that n also divides

an1+an2++a+1.

Problem 33

Find all the positive integers a such that 5a+13a is a positive integer.

Hints and Answers to Selected Problems

Problem 1

Answer: n=23k1s for some sN.

Problem 2

Show that vp(a1)=vp(ap1)1n1.

Problem 3

If a>1, a2+1 is not a power of 2 (because it is >2 and either 1 or 2 modulo 4). Choose some odd prime p|a2+1. Now, take some n=2m with odd m and notice that vp(4(an+1))= vp(a2+1)+vp(m) but vp(m) can be anything we want modulo 3.

Problem 5

2p+3p is not a square, and use the fact that v5(2p+3p)= 1+v5(p)2.

Problem 8

Consider two cases: p=2 and p is an odd prime. The latter does not give any solutions.

Problem 9

(n,m)=(2,1) is a solution. In other cases, show that n is an odd prime and m is even. The other solution is (n,m)=(5,2).

Problem 12

Answer: max(k)=1991.

Problem 13

Take any odd prime p such that p|a1. It’s clear that p2|aa11.

Problem 14

Answer: (p,x,y)=(2,1,1), (3,2,1).

Problem 18

Let p1=2sm and show that vp(2s1m)=0. The maximum of k is 1.

Problem 19

Try to prove Problem 15 first.

Problem 20

Show that p=2 and r is an even positive integer.

Problem 22

If p|a, p|b, then p3|a3+b3. Otherwise LTE applies and vp(a+b)= vp(a3+b3)2.

Problem 24

The answer is n=1 or n=3.

Problem 26

Answer: (p,q)=(3,3),(3,13).

Problem 27

If n is odd, then a=1. If n is even, then a=v2(5n3n)= v2(53)+v2(5+3)+v2(n)1= 3+v2(n). But, clearly, bv2(n).

Problem 30

n|(n1)n+1, so for every p|(n1)n+1, we have

vp((n1)(n1)n+1+1)=vp((n1)n+1)+vp((n1)n+1+1n)=2vp((n1)n+1)vp(n)

which completes the proof.

Problem 31

nv2(3n1)3+v2(n), so n4.

Problem 33

a must be odd (otherwise the numerator is 2mod3). Then av3(5a+1)= 1+v3(a) giving a=1 as the only solution.

Original sources

See Amir’s website here!
https://parvardi.com

Download the original PDF file (211 KB), published on April 2011.
https://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvNS8wLzgyODNhOGNhOWQ4OWM1NDk5NTY1MGQyNWVlYWNlMzE1OGYxMDM0&rn=TGlmdGluZyBUaGUgRXhwb25lbnQgLSBWZXJzaW9uIDYucGRm

References

1. Sepehr Ghazi Nezami, Leme Do Khat (in English: Lifting The Exponent Lemma), published on October 2009.

2. Kurt Hensel, Hensel’s lemma, WikiPedia.

3. Santiago Cuellar, Jose Alejandro Samper, A nice and tricky lemma (lifting the exponent), Mathematical Reflections 3 - 2007.

4. Amir Hossein Parvardi, Fedja et al., AoPS topic #393335, Lifting The Exponent Lemma (Containing PDF file).

5. Orlando Doehring et al., AoPS topic #214717, Number mod(f(m+n),p)=0 iff mod(f(m)+f(n),p)=0.

6. Fang-jh et al., AoPS topic #268964, China TST, Quiz 6, Problem 1.

7. Valentin Vornicu et al., AoPS topic #57607, exactly 2000 prime divisors (IMO 2000 P5).

8. Orlando Doehring et al., AoPS topic #220915, Highest degree for 3-layer power tower.

9. Sorush Oraki, Johan Gunardi, AoPS topic #368210, Prove that a=1 if 4(an+1) is a cube for all n.


Flotar

POLYNOMM. Regla y compás nunca ha de faltar...

Última modificación: 14 Mar 2021 (03:14 PM).