Lifting the exponent and math olympiad number theory

In math olympiads around the world, number theory problems have many recurring themes. One such theme is the ‘LTE’ or lifting the exponent.

Selective Logarithm

We define a function callled Selective Logarithm (SL) which works on all integers (positive, negative or zero). Suppose N is any integer and p be a prime then \[SL_p (N) = k \] where k is the highest power of p in that is a factor of N. In other words \[p^k \] divides N but \[p^{k+1} \] does not.

Illustration:

\[SL_3 (27) = SL_3 (54) = SL_3 (-108) = 3 \]

(Highest power of prime 3 in the prime factorization of each of them)

The SL function works like logarithm in some sense. For example we may easily prove and verify the following formulas:

1. \[SL_p (M times N) = SL_p M + SL_ p N \]
2. \[SL_p M^k = k SL_p M \]
3. \[SL_p 1 = 0 \]

We call this function ‘selective logarithm’ because it focuses on one prime factor and disregards all others. For example \[Sl_5 17 = 0 \] ; as 17 does not have any 5 in it’s prime factorization the SL function completely disregards thr magnitude of 17 and gives 0 as output.

Lifting the Exponent Theorem

\[SL_p ( x^n pm y^n ) = SL_p (x pm n ) + SL_p (n) \]

If p does not divides x and y and p divides \[x pm y \] . Additionally n has to be odd when we are working with \[x^n + y^n \]

We immediately see why the theorem gets it’s name. The exponent n is lifted from x and y and we are able to treat them separately.
Before we work on the proof of this theorem, some illustration problems and generalizations let us reiterate two familiar factorizations:

1. \[( x^n + y^n ) = ( x+ y )( x^{n-1} – y^1 x^{n-2} + y^2 x^{n-3} – … + y^{n-1} ) \] (n is odd)

2. \[( x^n – y^n ) = (x – y) ( x^{n-1} + y x^{n-2} + y^2 x^{n-3} + … y^{n-1} \]

Both of these factorizations, together with binomial theorem will be instrumental in the proof of Lifting the Exponent Theorem. In the next article of this series we will examine the proof and discuss some relevant problems.