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 —which is often — that divides for some positive integers and . 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 issues.
Definitions and Notation
For two integers and we say is divisible by and write if and only if there exists some integer such that .
We define to be the greatest power in which a prime divides ; in particular, if then but . We also write , if and only if . So we have and .
Example
The greatest power of that divides is , because but . In particular, or .
Example
Clearly we see that if and are two different prime numbers, then , or .
Note: We have for all primes .
Two Important and Useful Lemmas
Lemma 1
Let and be (not necessary positive) integers and let be a positive integer. Given an arbitrary prime (in particular, we can have ) such that , and neither , nor is divisible by (i.e., and ). We have
Proof
We use the fact that
Now if we show that , then we are done.
In order to show this, we use the assumption . So we have , or . Thus
This completes the proof.
Lemma 2
Let and be (not necessary positive) integers and let be an odd positive integer. Given an arbitrary prime (in particular, we can have ) such that , and neither , nor is divisible by , we have
Proof
Since and can be negative, using Lemma 1 we obtain
Note that since is an odd positive integer we can replace with .
Lifting The Exponent Lemma (LTE)
Theorem 1 First Form of LTE
Let and be (not necessary positive) integers, let be a positive integer, and let be an odd prime such that and none of and is divisible by (i.e., and ). We have
Proof
We may use induction on . First, let us prove the following statement:
In order to prove this, we will show that
and
For , we note that
Now, let , where is an integer. For an integer we have
This means
Using this fact, we have
So we proved and the proof of is complete. Now let us return to our problem. We want to show that
Suppose that where . Then
Note that we used the fact that if , then we have , because we have for all positive integers . The proof is complete.
Theorem 2 Second Form of LTE
Let , be two integers, be an odd positive integer, and be an odd prime such that and none of and is divisible by . We have
Proof
This is obvious using Theorem 1. See the trick we used in proof of Lemma 2.
What about ?
Question. Why did we assume that is an odd prime, i.e., ? Why can’t we assume that in our proofs?
Hint. Note that is an integer only for .
Theorem 3 LTE for the case
Let and be two odd integers such that . Then
Proof
We showed that for any prime such that , and none of and is divisible by , we have
Let be an odd integer and be a positive integer such that . So it suffices to show that
Factorization gives
Now since then we have for all positive integers and so Also, since and are odd and , we have . This means the power of in all of the factors in the above product (except ) is one. We are done.
Theorem 4
Let and be two odd integers and let be an even positive integer. Then
Proof
We know that the square of an odd integer is of the form . So for odd and we have . Now let be an odd integer and be a positive integer such that . Then
Summary
Let be a prime number and let and be two (not necessary positive) integers that are not divisible by . Then:
a. For a positive integer
if and , then
if and , then
if , is even, and , then
b. For an odd positive integer , if , then
c. For a positive integer with , if , we have
If is odd, , and , then we have
Note: The most common mistake in using LTE is when you don’t check the 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 for which there exist positive integers , and such that , and .
Solution
should be an odd integer (otherwise, if is even, then and are perfect squares, and it is well known that for integers , we have if and only if and , which is in contradiction with ).
Suppose that there exists a prime such that . This prime should be odd. So , and using Theorem 2 we have . But means that and so and so . Thus . This means for some positive integer . Note that . There are two cases:
We can prove by induction that for all integers , and so we have (why?). Let . Since , we have . Then
which is a contradiction.
Then , so , (or , ). Thus . But note that so . Thus
And one can check that the only odd value of that satisfies the above inequality is . So , in this case.
Thus, the final answer is .
Problem 2 Balkan 1993
Let be a prime number and be a positive integer. Show that if for some positive integers , we have
then .
Solution
One can prove by induction on that for all positive integers . Now since , we should have . Let , so there exist positive integers , with such that , and . There are two cases:
Assume that is odd.
Take any prime divisor of and let . If is odd, we see that and (because may also be a factor of ). Thus and , giving an immediate contradiction. If , then , so and , i.e., , which immediately implies .
Assume that .
We notice that for we have , so . It remains to check that the remaining cases are impossible.
Problem 3
Find all positive integers , that are greater than and satisfy
Solution
Let be the least prime divisor of . Let be the least positive integer for which . Then and , so any prime divisor of divides and is less than . Thus, not to run into a contradiction, we must have . Now, if is odd, we have , so , which is impossible. Thus , is even, is odd and whence , which is possible only if , . Put with odd and rewrite the condition as . Let be the least prime divisor of (now, surely, odd). Let be the least positive integer such that . Then and whence must be or (or has a smaller prime divisor), so or , which is impossible.
Thus and .
Problem 4
Find all positive integer solutions of the equation .
Solution
Factor . We have . Since and , we must have . Removing the highest possible power of from , (why?), we get a solution of the equation such that . We only need to check if there exists that solution. In that case, , so where . But we have , which means the only prime factor of is , so . Thus . But in this equation the left hand side is much larger than the right hand one if , and, clearly, is not a solution. Thus the given equation does not have any solutions in the set of positive integers.
Challenge Problems
Problem 1
Let be a positive integer. Find all positive integers such that .
Problem 2 UNESCO Competition 1995
Let , be two positive integers and let be an odd prime number such that
Prove that
Problem 3 Iran Second Round 2008
Show that the only positive integer value of for which is a perfect cube for all positive integers , is .
Problem 4
Let be an integer. Show that there exists infinitely many positive integers such that
Problem 5 Ireland 1996
Let be a prime number, and and positive integers. Prove that if
then .
Problem 6 Russia 1996
Let , , , , be positive integers such that is odd and is an odd prime. Prove that if , then is a power of .
Problem 7
Find the sum of all the divisors of which are of the form with .
Problem 8
Let be a prime number. Solve the equation in the set of positive integers.
Problem 9
Find all solutions of the equation
in positive integers.
Problem 10 Bulgaria 1997
For some positive integer , the number is a perfect power of a prime. Prove that is a prime.
Problem 11
Let , , be three positive integers with and . Show that if prime divisors of the numbers and be the same, then is a perfect power of .
Problem 12 IMO ShortList 1991
Find the highest degree of for which divides the number
Problem 13
Prove that the number is never square-free for all integers .
Problem 14 Czech Slovakia 1996
Find all positive integers , such that , where is a prime.
Problem 15
Let and be two positive rational numbers such that for infinitely many positive integers , the number is a positive integer. Show that and are both positive integers.
Problem 16 IMO 2000
Does there exist a positive integer such that has exactly prime divisors and divides ?
Problem 17 China Western Mathematical Olympiad 2010
Suppose that and are non-negative integers, and is a prime number. Prove that
is the smallest positive integer satisfying the congruence equation .
Problem 18
Let be a prime. Find the maximum value of positive integer such that
Problem 19
Let , be distinct real numbers such that the numbers
are all integers. Prove that , are both integers.
Problem 20 MOSP 2001
Find all quadruples of positive integers such that is a prime number, and .
Problem 21 China TST 2009
Let be positive integers and be an odd number, let be a positive integer. If , then show that .
Problem 22 Romanian Junior Balkan TST 2008
Let be a prime number, , and integers , such that and . Prove that or .
Problem 23
Let and be positive integers. Prove that for each odd positive integer there are infinitely many primes such that implies .
Problem 24 IMO 1990
Determine all integers such that
is an integer.
Problem 25
Find all positive integers such that
is an integer.
Problem 26
Find all primes , such that is an integer.
Problem 27
For some natural number let be the greatest natural number for which is divisible by . Also let be the greatest natural number such that . Prove that .
Problem 28
Determine all sets of non-negative integers , and which satisfy the equation
Problem 29 IMO ShortList 2007
Find all surjective functions such that for every and every prime , the number is divisible by if and only if is divisible by .
Problem 30 Romania TST 1994
Let be an odd positive integer. Prove that divides .
Problem 31
Find all positive integers such that is divisible by .
Problem 32 Romania TST 2009
Let be two integers, which have the following property: there exists an integer , such that divides . Prove that also divides
Problem 33
Find all the positive integers such that is a positive integer.
If , is not a power of (because it is and either or modulo ). Choose some odd prime . Now, take some with odd and notice that but can be anything we want modulo .
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.