Number theoretic lemma
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
in such expressions. 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.[3][4]
For any integers
, a positive integer
, and a prime number
such that
and
, the following statements hold:
- When
is odd:
- If
, then
.
- If
is odd and
, then
.
- If
is even and
, then
.
- When
:
- If
and
is even, then
.
- If
and
is odd, then
. (Follows from the general case below.)
- Corollaries:
- If
, then
and thus
.
- If
and
is even, then
.
- If
and
is odd, then
.
- For all
:
- If
and
, then
.
- If
,
and
odd, then
.
LTE has been generalized to complex values of
provided that the value of
is integer.[5]
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)
[edit]
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)
[edit]
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]
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
.[6]
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 residues 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.
- ^ 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&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
- ^ S. Riasat, Generalising `LTE' and application to Fibonacci-type sequences.
- ^ 2020 AIME I Problems. (2020). Art of Problem Solving. Retrieved July 11, 2020, from https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems