Lifting-the-exponent lemma

In elementary number theory, the lifting-the-exponent lemma provides several formulas for computing the p-adic valuation of special forms of integers. The lemma is named as such because it describes the steps necessary to "lift" the exponent of in such expressions. It is related to Hensel's lemma. Its main use is in mathematical olympiads.

Background

Although this lemma has been rediscovered many times and is now part of mathematical "folklore", its ideas appear as early as 1878 in the work of Édouard Lucas, who was then a professor at Lycée Charlemagne. Lucas described related divisibility results (with a minor error in the case p = 2). However, the modern and systematic formulation of the lemma, especially in the context of olympiad mathematics, was first published by Romanian mathematician Mihai Manea in 2006. The lemma has since become widely known by the informal name "LTE" (short for "Lifting The Exponent"), particularly through its use on mathematics forums such as the Art of Problem Solving. Despite chiefly featuring in mathematical olympiads, it is sometimes applied to research topics, such as elliptic curves.

Statements

For any integers and , a positive integer , and a prime number such that and , the following statements hold:

• When is odd:
• If , then .
• If and is odd, then .
• If and is even, then .
• When :
• If and is even, then .
• If and is odd, then . (Follows from the general case below.)
• Corollaries:
• If , and if both and are odd, then and thus .
• If and is even, then .
• If and is odd, then .
• For all :
• If and , then .
• If , and is odd, then .

Generalizations

The lifting-the-exponent lemma has been generalized to complex values of provided that the value of is an integer.

Proof outline

Base case

The base case when is proven first. Because ,

The fact that completes the proof. The condition for odd is similar, where we observe that the proof above holds for integers and , and therefore we can substitute for above to obtain the desired result.

General case (odd p)

Via the binomial expansion, the substitution can be used in () to show that because () is a multiple of but not . Likewise, .

Then, if is written as where , the base case gives . By induction on ,

A similar argument can be applied for .

General case (p = 2)

The proof for the odd case cannot be directly applied when because the binomial coefficient is only an integral multiple of when is odd.

However, it can be shown that when by writing where and are integers with odd and noting that

because since , each factor in the difference of squares step in the form is congruent to 2 modulo 4.

The stronger statement when is proven analogously.

In competitions

Example problem

The lifting-the-exponent lemma can be used to solve 2020 AIME I #12: <blockquote> Let be the least positive integer for which is divisible by Find the number of positive integer divisors of . </blockquote> Solution. Note that . Using the lifting-the-exponent lemma, since and , but , . Thus, . Similarly, but , so and .

Since , the factors of 5 are addressed by noticing that since the residues of modulo 5 follow the cycle and those of follow the cycle , the residues of modulo 5 cycle through the sequence . Thus, iff for some positive integer . The lemma can now be applied again: . Since , . Hence .

Combining these three results, it is found that , which has positive divisors.

References