In elementary number theory, the lifting-the-exponent lemma (LTE 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
It is related to Hensel's lemma.
The exact origins of the LTE lemma are unclear; the result, with its present name and form, has only come into focus within the last 10 to 20 years.
[1] However, several key ideas used in its proof were known to Gauss and referenced in his Disquisitiones Arithmeticae.
[2] Despite chiefly featuring in mathematical olympiads, it is sometimes applied to research topics, such as elliptic curves.
, a positive integer
, the following statements hold: LTE has been generalized to complex values of
provided that the value of
[5] The base case
completes the proof.
is similar, where we observe that the proof above holds for integers
above to obtain the desired result.
Via the binomial expansion, the substitution
, A similar argument can be applied for
case cannot be directly applied when
because the binomial coefficient
is only an integral multiple of
, each factor in the difference of squares step in the form
[1] The LTE lemma can be used to solve 2020 AIME I #12: Let
be the least positive integer for which
Find the number of positive integer divisors of
Using the LTE lemma, since
, the factors of 5 are addressed by noticing that since the residues of
modulo 5 follow the cycle
modulo 5 cycle through the sequence
for some positive integer
The LTE lemma can now be applied again:
Combining these three results, it is found that