Overview

The Lifting the Exponent Lemma, often abbreviated as LTE, is a powerful tool in olympiad number theory.

It helps determine how many times a prime divides expressions such as

or

In other words, LTE is useful when we want to compute the exponent of a prime inside a number.

For example, instead of just asking whether $3$ divides $10^6-1$, we can ask:

What is the largest power of $3$ that divides $10^6-1$?

LTE gives a fast and systematic way to answer questions like this.

Motivation

Consider

We can factor it as

or even further using difference of powers. However if we only care about powers of $3$, expanding or fully factoring the expression is inefficient.

Instead notice that

so $3$ divides $10-1$.

LTE tells us that under suitable conditions,

Since

and

we get

So $3^3$ divides $10^6-1$, but $3^4$ does not.

This kind of computation appears frequently in olympiad divisibility problems.

Prime Valuation

Before stating LTE, we need one piece of notation.

For a prime $p$ and a positive integer $N$, define

to be the exponent of $p$ in the prime factorisation of $N$.

In other words, $v_p(N)$ is the largest integer $k$ such that

Examples

Since

we have

and

Also,

because $5$ does not divide $72$.

This notation allows us to discuss divisibility by prime powers far more simply.

Main Statement: Difference Form

The most common version of LTE is the difference form.

Lifting the Exponent Lemma

Let $p$ be an odd prime. Suppose that $p\mid a-b$ and $p\nmid ab$. Then for every positive integer $n$,

This is the version used most often in olympiad problems.

Why the Conditions Matter

The assumptions are important.

• We require $p$ to be an odd prime.
• We require $p\mid a-b$.
• We require $p\nmid ab$.

The condition $p\mid a-b$ means that

The condition $p\nmid ab$ means that neither $a$ nor $b$ is divisible by $p$. This prevents degenerate cases where both powers contain extra factors of $p$ for unrelated reasons.

Intuition Behind LTE

The expression

always factors as

So $a-b$ is always a factor.

LTE says something more significant. If an odd prime $p$ divides $a-b$, then the additional powers of $p$ that appear in $a^n-b^n$ come from the exponent $n$.

That is why the formula is

The first term comes from the base difference $a-b$, and the second term comes from the exponent $n$.

Proof Sketch

We can outline the idea behind the proof for odd primes.

Write

where $p\mid h$.

Then

Using the binomial theorem,

The first term is

Since $p\nmid b$, the $p$-adic contribution of this term is essentially

The later terms contain higher powers of $h$, so they are more divisible by $p$. Under the hypotheses of LTE, these later terms do not change the final valuation.

Since

this gives

This proof sketch explains why the formula has the shape it does. A fully rigorous proof requires checking that the later binomial terms have large enough $p$-adic valuation.

Worked Examples

Example 1

Find the largest power of $3$ dividing $10^6-1$.

We use LTE with

Since

and

the conditions are satisfied.

Therefore,

Now

and

Thus

So the largest power of $3$ dividing $10^6-1$ is $3^3$.

Part 2: Check the part 2 for continuation