The "lifting the exponent" (LTE) lemma is a useful one about the largest power of a prime dividing a difference or sum of powers. Here are some sample problems whose solutions use the lemma:
- Let be a square-free integer. Show that there is no pair of coprime positive integers such that
- Show that is a primitive root mod for all positive .
- Find all solutions in positive integers to , where , .
- Suppose and are positive real numbers such that are all positive integers. Show that and must be positive integers.
Let be a prime and a nonzero integer. Then we define to be the exponent of in the prime factorization of . That is,
Let be a prime, and integers, a positive integer, and suppose that but and . Then
(1) if is odd, (2) for and even ,
Notice that if is odd, we can substitute for in (1) to obtain
Use the LTE lemma to find the largest power of dividing .
So the answer is .
Without LTE, the problem can be solved by factoring
The first factor has one and the fourth factor has no s, and some careful mod- analysis shows that the second and third factors are divisible by but not , so the total number of factors of is . This is quite a bit more complicated (but note that it also indicates how an inductive proof of LTE might proceed).
This lemma gives a practical way to solve many problems involving the largest power of a prime that divides certain expressions. In particular, the solutions to the problems in the introduction all use LTE in an essential way.
As a warmup, here is a typical Diophantine equation that can be tackled using the LTE Lemma.
Let be a square-free integer. Show that there is no pair of coprime positive integers such that
Assume with . We will derive a contradiction.
First, suppose is even. If there is an odd prime , then mod , so , so , contradiction. Since and are positive, the only possible way that there is no odd prime dividing is if is a power of . In this case, and are both odd since they are coprime, so since is even and are both mod , it follows that , but , so again we get a contradiction.
Now suppose is odd. If there is an odd prime , then . Then LTE gives
since is square-free. Simplifying, we get , which is impossible since .
As above, the only remaining case is when is a power of . But in this case, if is odd, because and are odd and the expansion of
has an odd number of terms, all of which are odd. So it is impossible for to divide , since the power of on the left exceeds the power of on the right.
Show that is a primitive root mod for all positive .
We seek the smallest positive such that mod . If , first note that mod , so is even. Write . So . Now LTE applies:
So . The smallest possible such is , so the smallest possible is , where is Euler's totient function. This proves the claim.
Here is a similar problem to try:
Find all solutions in positive integers to , where , .
If one of or is divisible by , then they both are, which is a contradiction. So neither is. If is even, then and are both mod , so is not divisible by any power of .
Now suppose is odd. If then , and there are no solutions to this in positive integers, so we can exclude this case. Since , . Apply LTE:
The point is that the left side is usually much bigger than the right side, so the result will follow from some routine inequalities.
Suppose without loss of generality. Then dividing through by gives
The left side is , so . So . Recall . By calculus, the right side is decreasing for , so , so . We already ruled out , so and hence .
In that case already unless , but is odd so . It's easy to check that is a solution, as is if we relax the assumption, and the above analysis has shown that these are the only ones.
Suppose and are positive real numbers such that are all positive integers. Show that and must be positive integers.
Since and , . But then and are rational numbers as well.
Now, write and as quotients of positive integers, with a common denominator. Choose as small as possible. Then the conditions of the problem imply that
Suppose is a prime dividing . Note so . If then as well, but that violates the choice of : we could write to get a smaller common denominator.
So and we are set up to apply LTE. If is odd, then
Taking to both sides gives
but this is impossible since the left side goes to infinity as , and the right side is a constant independent of .
If we get
and we get a similar contradiction.
The conclusion is that there is no prime dividing . So and and are both positive integers.
Here is an outline of the proof for odd primes ; the proof for is similar. Suppose , .
Step 0: If , then
To see this, write , and since mod this becomes
which is nonzero since and .
Step 1: Prove it for .
In this case, , so the idea is to show that the latter term equals .
To do this, write for some , and expand as a polynomial in , looking mod throwing out terms with or higher Eventually we get
So it is divisible by but not , as desired.
Step 2: Write , , and use the previous two steps repeatedly.
and iterating the last two lines (or using induction) eventually gives , which is .