In elementary number theory, the lifting-the-exponent (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
in such expressions. It is related to Hensel's lemma.
Background
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.[3][4]
Statements
For any integers
and positive integers
and
, where
is a prime such that
and
, the following identities hold:
- When
is odd:
- If
,
.
- If
is odd and
,
.
- When
:
- If
,
.
- If
,
.
- For all
:
- If
,
.
- If
with
odd,
.
Outline of proof
Base case
The base case
when
is proven first. Because
,
![{\displaystyle x^{n-1}+x^{n-2}y+x^{n-3}y^{2}+\dots +y^{n-1}\equiv nx^{n-1}\not \equiv 0{\pmod {p}}\ (1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/94d60c263ed65e91f1aa36c66ba264fdd35976fa)
The fact that
completes the proof. The condition
for odd
is similar.
General case (odd p)
Via the binomial expansion, the substitution
can be used in (1) to show that
because (1) is a multiple of
but not
.[1] Likewise,
.
Then, if
is written as
where
, the base case gives
.
By induction on
,
![{\displaystyle {\begin{aligned}\nu _{p}(x^{p^{a}}-y^{p^{a}})&=\nu _{p}(((\dots (x^{p})^{p}\dots ))^{p}-((\dots (y^{p})^{p}\dots ))^{p})\ {\text{(exponentiation used }}a{\text{ times per term)}}\\&=\nu _{p}(x-y)+a\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76d7e4b5009910e56b7aa28cab95797b528bae83)
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
![{\displaystyle {\begin{aligned}\nu _{2}(x^{n}-y^{n})&=\nu _{2}((x^{2^{a}})^{b}-(y^{2^{a}})^{b})\\&=\nu _{2}(x^{2^{a}}-y^{2^{a}})\\&=\nu _{2}((x^{2^{a-1}}+y^{2^{a-1}})(x^{2^{a-2}}+y^{2^{a-2}})\cdots (x^{2}+y^{2})(x+y)(x-y))\\&=\nu _{2}(x-y)+a\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/280d671a08ffe6efeba9338f93edf07309e9c5f8)
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.[1]
In competitions
Example problem
The LTE lemma can be used to solve 2020 AIME I #12:
Let
be the least positive integer for which
is divisible by
Find the number of positive integer divisors of
.[5]
Solution. Note that
. Using the LTE 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 resiudes of
modulo 5 cycle through the sequence
. Thus,
iff
for some positive integer
. The LTE lemma can now be applied again:
. Since
,
. Hence
.
Combining these three results, it is found that
, which has
positive divisors.
References
- ^ a b c Pavardi, A. H. (2011). Lifting The Exponent Lemma (LTE). Retrieved July 11, 2020, from http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.221.5543 (Note: The old link to the paper is broken; try https://s3.amazonaws.com/aops-cdn.artofproblemsolving.com/resources/articles/lifting-the-exponent.pdf instead.)
- ^ Gauss, C. (1801) Disquisitiones arithmeticae. Results shown in Articles 86–87. https://gdz.sub.uni-goettingen.de/id/PPN235993352?tify={%22pages%22%3A%5B70%5D}
- ^ Geretschläger, R. (2020). Engaging Young Students in Mathematics through Competitions – World Perspectives and Practices. World Scientific. https://books.google.com/books?id=FNPkDwAAQBAJ&lpg=PA3&ots=rkjtruFbsM&lr&pg=PP1
- ^ Heuberger, C. and Mazzoli, M. (2017). Elliptic curves with isomorphic groups of points over finite field extensions. Journal of Number Theory, 181, 89–98. https://doi.org/10.1016/j.jnt.2017.05.028
- ^ 2020 AIME I Problems. (2020). Art of Problem Solving. Retrieved July 11, 2020, from https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems