Lifting the exponent
Carl Joshua Quines
July 20, 2019
Valuation
Define νp (n) for positive integers n as
νp (n) = k ⇐⇒ pk | n, pk+1 - n.
This is known as the p-adic valuation of n. Note that this is νp with the Greek letter ν (spelled nu,
pronounced “new”).1 Some properties that you should convince yourself are true:
• νp (ab) = νp (a) + νp (b).
• Similarly νp ab = νp (a) − νp (b). We can use this to extend the definition of νp to be a function
from Q6=0 → Z.
What should νp (0) be? To satisfy the product rule, we can pick νp (0) = ∞.
• νp (a + b) ≥ min {νp (a), νp (b)}, equality holds if νp (a) 6= νp (b).
• νp (a − b) ≥ e ⇐⇒ a ≡ b (mod pe ) from the previous.
• νp (gcd(a, b)) = min {νp (a), νp (b)}.
• νp (lcm(a, b)) = max {νp (a), νp (b)}.
• a = b ⇐⇒ νp (a) = νp (b) for all p.
• More generally, a | b ⇐⇒ νp (a) ≤ νp (b) for all p.
Examples
abc · lcm(a, b, c)
1. Prove that gcd(a, b, c) = .
lcm(a, b) lcm(b, c) lcm(c, a)
Sketch: Pick a prime p, idea is to show νp of LHS and RHS are the same. Let x =
νp (a), y = νp (b), and z = νp (c). In the LHS you have min {x, y, z}, on the RHS you have
x + y + z + max {x, y, z} − max {x, y} − max {y, z} − max {z, x}. But these are equal.
2. Suppose a | b2 | a3 | b4 | a5 | · · · . Prove that a = b.
Sketch: This is an easy problem, but it’s a bit hard to write up. Using νp makes it easier.
We have
2n
a2n−1 | b2n =⇒ (2n − 1)νp (a) ≤ 2nνp (b) =⇒ νp (a) ≤ νp (b).
2n − 1
Taking the limit as n → ∞ means νp (a) ≤ νp (b); similarly we can prove νp (b) ≤ νp (a). This
shows νp (a) = νp (b).
1
This is sometimes written as vp with the English letter v. I don’t think this is standard, as I see more sources use
νp . I don’t even know why ν is the letter chosen for this, other than its superficial similarity to the letter v.
1
3. Let p prime, n ∈ N. Suppose p || 2n − 1. Show that p || 2p−1 − 1. (We say p || n ⇐⇒ p |
n, p2 - n.)
Remark: While this is typically done with the so-called lifting the exponent lemma, many
people learn the statement without knowing the proof, which I think is bad, because the proof
gives useful intuition. So we’re going to motivate the proof using this problem and the next
problem.
Sketch: Let m be the order of 2 modulo p. That is, the smallest positive integer m such
that p | 2m − 1. Because m is the order, we have m | n, so 2m − 1 | 2n − 1, therefore, we get
p || 2m − 1.
Now we use the main idea, and that’s dividing 2p−1 − 1 by 2m − 1. With some algebra,
2p−1 − 1
= 1 + 2m + 22m + · · · + 2p−1−m .
2m − 1
Modulo p, this is p−1 m 2
m (because p | 2 − 1). So this is not equal to 0, so p - 2
p−1 − 1. But by
FLT, p | 2 p−1 − 1, the conclusion follows.
n
4. Let n ∈ N0 . Find ν3 23 + 1 .
Sketch: This is induction. Find the answer when n = 0. Then observe that
n+1
23 +1 n n
= 22·3 − 23 + 1 ≡ 1 − (−1) + 1 ≡ 3 (mod 9),
23n + 1
then it’s divisible by 3 but not 9, so going n → n + 1 increases ν3 by 1.
Lifting the exponent
We can now state and prove the lifting the exponent lemma. It states that if p is an odd prime,
p - a, p - b, and p | a − b, then
νp (an − bn ) = νp (a − b) + νp (n)
for all positive integers n. The condition p | a − b is very important, yet easy to forget.
Always remember to check this condition. In particular, you must have νp (a − b) > 0.
The proof is by induction on n. The main idea here is the inductive step. The idea is that we
want to take out the powers of p from n. For example, if we take n = pα , we can rewrite this as
α−1 p α−1 p α−1 α−1
νp ap − bp = νp ap − bp + 1.
But to prove this, we only have to show that it’s true for n = p. Similarly, if we have n = pα β,
where gcd(p, β) = 1, we can write
α β α β
α α
νp ap − bp = νp ap − bp ,
which means we only have to show the case when νp (n) = 0. This is already our inductive step! So
these two cases, the one where νp (n) = 0 and n = p, will form the two base cases of our induction.
The case νp (n) = 0 is easy. Write
p
a − bp
n n
νp (a − b ) = νp (a − b) ⇐⇒ νp = 0;
a−b
2
where we get the second equation by transposing νp (a − b) and applying the quotient rule. We only
need to show that
p - ap−1 + ap−2 b + · · · + bp−1 .
This follows because a ≡ b (mod p), so substitute this to get
ap−1 + ap−1 + · · · + ap−1 ≡ nap−1 6≡ 0.
The other base case, n = p, is harder. We need to show that
ap − bp
p p
νp (a − b ) = νp (a − b) + 1 ⇐⇒ νp = 1.
a−b
There are two parts here. First, we want to show
p | ap−1 + ap−2 b + · · · + bp−1 .
This follows because a ≡ b (mod p), so using a similar process from the other base case, we get
pap−1 ≡ 0. Second, we want to show that
p2 - ap−1 + ap−2 b + · · · + bp−1 .
This second part is an algebra bash. We substitute b ≡ pk + a (mod p2 ), then expand with the
binomial theorem. It’s not that bad because all of the terms with p2 disappear, leaving us with
ap−1 + ap−1 + ap−2 pk + ap−1 + 2ap−2 pk + · · · + ap−1 + (p − 1)ap−2 pk .
The ap−2 pk terms have coefficients 1 + 2 + · · · + p − 1 ≡ 0 (mod p), so coupled with the extra p
factor, they all sum to 0 (mod p)2 . This leaves you with pap−1 6≡ 0 (mod p2 ).
An alternative formulation follows if n is odd. Then we can replace b with −b to get
νp (an + bn ) = νp (a + b) + νp (n).
Note, again, this only applies if n is odd.
Example: Suppose a, b, n, p, k ∈ N such that n > 1 is odd, p is an odd prime, and an + bn = pk .
Prove that n is a power of p.
Sketch: Check all the conditions before using LTE! We have p is an odd prime. If p | a,
then p | b, and we can divide both a and b by p until neither is divisible by p, so WLOG p - a and
p - b. Also, n is odd so we can use the + case of LTE.
Now we check the hard condition. By factorization, since a + b | an + bn = pk , it must follow that
either a + b = 1 (impossible) or p | a + b. This gives us all the conditions and now we can use LTE:
k = νp pk = νp (an + bn ) = νp (a + b) + νp (n).
Now suppose ` = pνp (n) . Then
νp a` + b` = νp (a + b) + νp (n).
So pk | a` + b` | an + bn = pk , so they must all be equal and n = ` which is a power of p.
3
Problems
1. (Folklore) Fix k ∈ N. Find all n such that 3k | 2n − 1.
2. (Iran 2008) Fix a ∈ N. Suppose 4(an + 1) is a perfect cube for all n ∈ N. Prove that a = 1.
3. (Ireland 1996) If 2p + 3p = an for some prime p, prove n = 1.
1992 1990
4. (ISL 1991) Find the largest k such that 1991k | 19901991 + 19921991 .
5. (AIME 2018) Find the smallest n such that 3n ends with 01 when written in base 143.
Hints
1. 22n − 1 = 4n − 1 and 3 | 4 − 1.
2. Taking a2 + 1 mod 4, we see it’s never a power of 2.
3. 2p + 3p is not a square. Find ν5 (2p + 3p ).
1990
2 1991
1992
4. 19901991 = 19901991 .
5. 11 | 35 − 1 so 3n − 1 = (35 )n/5 − 1.
References
The classic reference is Amir Hossein Parvardi’s Lifting the Exponent Lemma handout, but I
don’t think it motivates LTE well enough. The exposition here roughly follows Evan Chen’s OTIS
Excerpts.
Thanks to Konwoo Kim for sending a correction.