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.

Advertisements

1 thought on “Lifting the exponent and math olympiad number theory”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s