Gaussian Curvature

Mohammed Imran, Aniruddha07, phoenixfire

 CONTENTS I

Contents

Contents I
0.1 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1 The yoga of p-adic valuations 2

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Lifting the Exponent Lemma (LTE) . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Zsigmondy’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2 Legendre’s Formula 26
2.1 The p-adic valuation of n! . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3 Practice Problems 30
3.1 Introduction and LTE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Zsigmondy’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Legendre’s Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
 Acknowledgements 1

0.1 Acknowledgements

This handout is one of the many handouts of Gaussian Curvature. This handout is intended
for Intermediate to Advanced problem solvers in Number Theory; it covers topics like LTE,
Zsigmondy’s, Legendre’s Formula and etcetra. This handout is authored by Mohammed Imran
aka Rama1728, Aniruddha Sharma aka Aniruddha07, and phoenixfire. Nevertheless, Mr.C
pointed out numerous errors and helped to improve the manuscript. We are also thankful to
the several users on AoPS who posted problems and solutions and many resources which we
noted down or also we forgot some to refer to. We hope that this handout is error free. We
also hope that you find this handout helpful.

Note. We are humans and are bound to make mistakes. If you find any, feel free to mail
them at gaussiancurvature360@gmail.com
 Introduction CHAPTER 1. THE YOGA OF p-ADIC VALUATIONS 2

Chapter 1

The yoga of p-adic valuations

In this chapter, we aim to do a rather detailed study of the p-adic valuations map v p : N → N,
where p is a fixed prime.

We now introduce a very important definition: If n is a positive integer more than 1, then
v p (n) is the power of p in the prime factorization of n.

After surfing through the basic properties of the map v p , we will use them to derive some
important and intriguing results.

1.1 Introduction

Let p be a fixed prime. It will be more convenient if we extend the map v p : N → N to a

map v p : Z → N ∪ {∞} by defining v p (n) = v p (|n|) for all n ∈ N/{0, ±1}, v p (±1) = 0 and
v p (0) = ∞. In other words, we say that v p (n) is the largest nonnegative integer k such that
pk |n. In particular, if v p (n) ≥ 1, then p|n.
We call v p (n) as the p-adic valuation of n.

After familiarizing ourselves with the definitions, we can now move on to some elementary
properties of the map v p .

Properties:

˜ For integers a, b and prime p, we have v p (ab) = v p (a) + v p (b)

˜ For integers a, b with b|a and prime p, we have v p ( ba ) = v p (a) − v p (b)

˜ For integer a and nonnegative integer n, we have v p (an ) = nv p (n)

˜ For integers a, b and prime p with v p (a) > v p (b), we have v p (a + b) = v p (b)
 Introduction 3

Presented below is a theorem which contains some of the elementary properties of p-adic
valuations.

Theorem 1.1.1 (Basic Properties) — a) If n is a non-zero integer, then we can write

n = pv p (n) · m, where m is an integer with gcd(m, p) = 1
b) For each n > 1 we have
n = ∏ pv p (n)
p|n

c) For all integers a, b we have

v p (ab) = v p (a) + v p (b) and v p (a + b) ≥ min(v p (a), v p (b))

Proof. a) Note that if p|n, and v p (n) = k, then clearly from the definition of the map
v p , we have pv p (n) = pk |n. So, n = pv p (n) · m for some integer m. Note that m cannot be
divisible by p, as if it was, then pk+1 |n, implying that v p (n) ≥ k + 1 contradicting
  the fact
k v (n)


that v p (n) = k. So, we must have 1 = gcd(m, p) = gcd m, p = gcd m, p p and we
are done.
b) Let n = P1a1 · P2a2 · · · Pkak . Then, note that vPi (n) = ai for i = 1, 2, 3, · · · k. Thus,

k k
vPi (n)
n=∏ Piai = ∏ Pi = ∏ pv p (n)
i=1 i=1 p|n

and we are done.

c) Note that this is obvious when one of a or b is 0, so suppose ab 6= 0. By a), we can
write a = pv p (a) ·u and b = pv p (b) ·v, where gcd(u, p) = gcd(v, p) = 1. Then, gcd(uv, p) = 1
and ab = pv p (u)+v p (v) · (uv). Hence v p (a) + v p (b) = v p (ab). Next, pmin(v p (a),v p (b)) divides
both a and b, and hence it divides a + b. Therefore, v p (a + b) ≥ min (v p (a), v p (b)), with
equality if and only if v p (a) 6= v p (b).

The following theorem although quite elementary is the root to tackling various complex prob-
lems.

Theorem 1.1.2 — If a, b are integers then a|b if and only if v p (a) ≤ v p (b) for all primes
p.

Proof. Without loss of generality, let a and b be non-zero. Then, if a|b, and b = ac, we
have v p (b) = v p (a) + v p (c) ≥ v p (a) for every prime p. Now, assume that v p (b) ≥ v p (a)
for all primes p. Then according to Theorem 1.1.1 b), we have

a = ∏ pv p (a) and b = ∏ bv p (b)

p p
 Introduction 4

where the product ranges for all primes p. Since v p (a) ≤ v p (b) for all primes p, the
powers of the primes in the prime factorisation of b is greater than or equal to that of a.
Therefore, we have a|b, and we may conclude.

Remark. This theorem has an interesting consequence:

If a, b are integers then an |bn if and only if a|b
The proof of this is left for the reader as an easy exercise.

Consequently, one may wonder whether or not there exists a connection between powers of
integers and their p-adic valuations. The answer is yes. We present a theorem explaining the
connection.

Theorem 1.1.3 — Let a and n be positive integers. Then a is a nth power of an integer
if and only if v p (a) ≡ 0(mod n).

Proof. First, let a = bn for some integer b. Then,

v p (a) = v p (bn ) = nv p (b) ≡ 0(mod n)

Next, let v p (a) = n · b p .Then,

a = ∏ pv p (a) = ∏ pn·b p = (∏ pb p )n = bn
p p p

and we are done.

Remark. This theorem has an immediate and interesting result:

If a and b are relatively prime numbers such that ab is a perfect nth power, then so are a and b.
The proof of this is left for the reader as an easy exercise.

Lemma 1.1.4 — For all integers a and b we have

v p (gcd(a, b)) = min (v p (a), v p (b)) and v p (lcm(a, b)) = max (v p (a), v p (b))

Proof. If one of a or b is 0, then this is trivial. Thus, we may assume that ab 6= 0.

Now let a = pa1 · a2 andb = pb1 · b2 , where a1 and b1 are nonnegative integers. Then,
gcd(a, b) = pmin(a1 ,b1 ) · gcd(a2 , b2 ), where v p (a2 ) = v p (b2 ) = 0. Thus, if we assume a1 ≤
b1 , then we have

v p (gcd(a, b)) = v p (pa1 ) + v p (gcd(a2 , b2 )) = a1 = min(v p (a), v p (b))

 Introduction 5

where the second-last equality follows from the fact that v p (gcd(a2 , b2 ) = 0(since a2 and
b2 are not divisible by p, their gcd is not divisible by p, and hence v p (gcd(a2 , b2 ) = 0).
We may now conclude.
The proof of the second part of the problem is left as an exercise for the reader.

Remark. Note that, we can generalize this lemma to:

v p (gcd(x1 , x2 , · · · xn )) = min v p (xi )
1≤i≤n

and
v p (lcm(x1 , x2 , · · · xn )) = max v p (xi )
1≤i≤n
for arbitrary integers x1 , x2 , · · · xn .

We shall now move on and tackle some concrete and challenging problems.

Problem 1. Show that a rational number q is an integer if and only if v p (q) ≥ 0 for every
prime p.

Solution. Let q = ba , where a and b are relatively prime integers. Then, v p (q) =
v p (a) − v p (b). Thus, it suffices to show that b | a if and only if v p (a) ≥ v p (b), but this is
exactly what we showed in Theorem 1.1.2!

Problem 2. Prove the identity

2 gcd(a, b, c)2
lcm(a, b, c) lcm(a, b) · lcm(b, c) · lcm(c, a) =
gcd(a, b) · gcd(b, c) · gcd(c, a)
for all positive integers a, b, c.

Solution. Let for all primes p, v p (a) = x p , v p (b) = y p and v p (c) = z p . Then, taking the
p-adic valuations on both sides of the equality we have to prove, it suffices to show that

lcm(a, b, c)2 gcd(a, b, c)2

   
vp = vp
lcm(a, b) · lcm(b, c) · lcm(c, a) gcd(a, b) · gcd(b, c) · gcd(c, a)

for all primes p. This is equivalent to each of the following:

v p (lcm(a, b, c)2 ) − v p ∏(lcm(a, b)) = v p (gcd(a, b, c)2 ) − v p ∏(gcd(a, b))

cyc cyc

2v p (lcm(a, b, c)) − ∑(v p (lcm(a, b)) = 2v p (gcd(a, b, c)) − ∑(v p (gcd(a, b))
cyc cyc
 Introduction 6

2 max(x p , y p , z p ) − ∑ max(x p , y p ) = 2 min(x p , y p , z p ) − ∑ min(x p , y p )

cyc cyc

Now, since this equation is symmetric, we can assume that x p ≤ y p ≤ z p . Then,it suffices
to prove that
2x p − x p − y p − x p = 2z p − z p − y p − z p
which is clear. This completes the proof.

Remark. This problem can also be solved using the fact that
xy
lcm(x, y) =
gcd(x, y)

The rest of the proof is left for the reader as an easy exercise.

Problem 3 (IMO 1974 Shortlist). Let a1 , a2 , · · · , ak and b1 , b2 , · · · , bk be positive integers

such that gcd(ai , bi ) = 1 for all 1 ≤ i ≤ k. Prove that
 
a1 m a2 m ak m
gcd , ··· , = gcd(a1 , a2 , · · · , ak )
b1 b2 bk

where m = lcm(b1 , b2 , · · · , bk )

Solution. Fix a prime p and let xi = v p (ai ) and yi = v p (bi ). By hypothesis, we have
min(xi , yi ) = 0 for all i and we need to prove that if

z = max(y1 , y2 , · · · , yk ),

then
min(x1 − y1 + z, x2 − y2 + z, · · · , xk − yk + z) = min(x1 , x2 , · · · , xk )
Note that xi − yi + z ≥ xi for all i, so the right hand side is at least the left hand side. Now,
if z = 0, then our assumption forces all yi to be 0 and the equality is clear. Otherwise, let
y j = z > 0 for some j, forcing x j = 0, implying x j − y j + z = 0 and we may conclude.

Problem 4. Prove that for all n ≥ 2, we have

lcm(1, 2, 3, · · · , n) ≤ nπ(n)

where π(n) is the number of primes below n.

Solution. We prove a lemma,

 Introduction 7

Lemma 1.1.5 — If n > 1 is an integer and p a prime, then

 
v p (lcm(1, 2, 3, · · · , n)) = log p (n)

Proof. By lemma 1.1.4, we have

v p (lcm(1, 2, 3, · · · , n)) = max v p (i)

1≤i≤n

Let k = log p (n) , so that pk ≤ n < pk+1 . Then, for any i ∈ {1, 2, 3, · · · , n} is i divisile
 

by pk+1 and so
max v p (i) = v p (pk ) = k
1≤i≤n

as desired. This completes the proof.

Returning to the problem, by our lemma we have

pv p (lcm(1,2,3,··· ,n)) ≤ n

and multiplying for all primes p less than n yields the desired result. This settles the proof.

Problem 5 (IMO 2007 Shortlist). Let b, n > 1 be integers. Suppose that for each k > 1,
there exists an integer ak such that b − ank is divisible by k. Prove that b = An for some integer
A.

Solution. Let the prime factorization of b be b = pα1 1 · pα2 2 · · · pαs s . It suffices to show
that all the exponents αi are divisible by n. Apply the condition for k = b2 . The number
b − ank is divisible by b2 and hence, for each 1 ≤ i ≤ s, it is divisible by p2α i αi
i > pi as well.
Therefore,
ank ≡ b ≡ 0(mod pαi i )
and
ank ≡ b 6≡ 0(mod pi i+1 )
α

which implies that the largest power of pi dividing ank is pαi i . Since ank is a complete nth
power, this implies that αi is divisible by n as desired.

Problem 6. Prove that

n
1
∑i
i=1
is not an integer for n ≥ 2.
 Introduction 8

Solution. The key idea for the problems is to find a prime that divides into the denom-
inator more than in the numerator. Notice that
n n n!
1
∑ i = ∑ n!i
i=1 i=1
!
n
n!
We consider v2 ∑ i . Then, as
i=1
   
n! n!
v2 > v2
2i − 1 2i

we have    
n! n! n!
v2 + = v2
2i − 1 2i 2i
     
n! n! n!
We then get v2 + = v2 and repeating to sum up the factorial in
4i − 2 4i 4i
this way we arrive at !
n  
n! n!
v2 ∑ = v2 blog nc
i=1 i 2 2
n
1
However for ∑i to be an integer we need
i=1
!
n
n!
v2 ∑i ≥ v2 (n!)
i=1
 
n!
v2 ≥ v2 (n!)
2blog2 nc
0 ≥ blog2 nc
a contradiction. This completes the proof.

Problem 7 (Saint Petersburg Olympiad 2006). Let a1 , a2 , ..., a101 be positive integers
such that gcd(a1 , a2 , . . . , a101 ) = 1 and the product of any 51 of these numbers is divisible by
the product of the remaining 50. Prove that a1 a2 . . . a101 is a perfect square.

Solution. To show that a1 a2 . . . a101 is a perfect square, it’s equivalent

to showing that given a prime number p that divides a1 a2 . . . a101 , we have
v p (a1 a2 . . . a101 ) = v p (a1 ) + v p (a2 ) + . . . + v p (a101 ) is an even integer.

From the given fact that gcd(a1 , a2 , . . . , a101 ) = 1, we get

min{v p (a1 ), v p (a2 ), . . . , v p (a101 )} = 0. This means that there must be at least one
 Introduction 9

ai such that v p (ai ) = 0. WLOG, let v p (a1 ) ≥ v p (a2 ) ≥ . . . ≥ v p (a101 ) = 0, by the second
given property, we have

v p (a1 ) + v p (a2 ) + . . . + v p (a50 ) ≤ v p (a51 ) + v p (a52 ) + . . . + v p (a101 )

and

v p (a1 ) + v p (a2 ) + . . . + v p (a50 ) + v p (a101 ) ≥ v p (a51 ) + v p (a52 ) + . . . + v p (a100 ).

Now, notice that since v p (a101 ) = 0, we have

v p (a1 ) + v p (a2 ) + . . . + v p (a50 ) ≤ v p (a51 ) + v p (a52 ) + . . . + v p (a100 )

and
v p (a1 ) + v p (a2 ) + . . . + v p (a50 ) ≥ v p (a51 ) + v p (a52 ) + . . . + v p (a100 )
which means

v p (a1 ) + v p (a2 ) + . . . + v p (a50 ) = v p (a51 ) + v p (a52 ) + . . . + v p (a100 )

and so

v p (a1 a2 . . . a101 ) = v p (a1 ) + v p (a2 ) + . . . + v p (a101 ) = 2(v p (a1 ) + v p (a2 ) + . . . + v p (a50 )).

This shows a1 a2 . . . a101 is a perfect square.

Problem 8. Find all positive integers a and b for which (a + b2 )(a2 + b) is a power of 2.

Solution. We will prove that a = b = 1 is the unique solution of the problem. Assume
that (a, b) 6= (1, 1) and without loss of generality, that a > 1. Write a + b2 = 2m and
b + a2 = 2n for some m, n ≥ 1. If a is even then so is b and since v2 (a) < m = v2 (2m ), we
have v2 (2m − a) = v2 (a), thus

2v2 (b) = v2 (b2 ) = v2 (2m − a) = v2 (a),

and similarly 2v2 (a) = v2 (b), contradicting our assumption that v2 (a) > 0.
Hence a is odd. If b > 1, then a similar argument as above yields

v2 (b + 1) < v2 (b2 − 1) = v2 (2m − (a + 1)) = v2 (a + 1)

and
v2 (a + 1) < v2 (a2 − 1) = v2 (2n − (b + 1)) = v2 (b + 1)
a contradiction. Thus the only possible solution is (a, b) = (1, 1).

Problem 9 (Erdos-Turan). Let a1 < a2 < · · · be an increasing sequence of positive integers.

 Introduction 10

Prove that for any N we can find i 6= j such that ai + a j has a prime factor greater than N.

Solution. Fix N and let p1 , p2 , · · · pk be all primes not exceeding N. Suppose that for
all i 6= j, all prime factors of ai + a j are among p1 , p2 , · · · , pk . Fix any positive integer d
greater than all the numbers av −au with 1 ≤ u < v ≤ k +1. Fix also n > (p1 p2 · · · pk )d and
note that for all 1 ≤ i ≤ n we have an +ai > (p1 p2 · · · pk )d , thus there is ji ∈ {1, 2, 3, · · · , k}
such that v pi j (an + ai ) > d. Since j1 , j2 , · · · , jk+1 are all between 1 and k, two of them
must be equal, say ju = jv with 1 ≤ u < v ≤ k + 1. Let p = p ju , so that v p (an + au ) > d
and v p (an + av ) > d. It follows that v p (av − au ) > d contradicting the fact that d is greater
than av − au . This completes the proof.

Problem 10 (IMO Shortlist 2009). Let f : N → N be a non-constant function such that

a − b divides f (a) − f (b) for all a, b ∈ N. Prove that there exist infinitely many primes p such
that p divides f (c) for some positive integer c.

Solution. Suppose that the conclusion fails and let p1 , p2 , · · · , pk be all primes appearing
in the prime factorizations of the numbers f (1), f (2), · · ·. Take any positive integer x
and write f (x) = pα1 1 pα2 2 · · · pαk k for some non-negative integers α1 , α2 · · · αk . Let as =
spα1 1 +1 pα2 2 +1 · · · pαk k +1 for s ≥ 1. Since as divides f (x + as ) − f (x) and since v pi ( f (x)) <
v pi (as ), it follows that v pi ( f (x + as )) = v pi ( f (x)) for all i. But since all prime factors
of f (x + as ) are among p1 , p2 , · · · , pk , it follows that f (x + as ) = f (x), and this holds
for all s ≥ 1. But then x + as − 1 divides f (x) − f (1) = f (x + as ) − f (1) for all s ≥ 1, so
f (x) = f (1). Since x was arbitrary, this means that f is a constant function, contradicting
the hypothesis of the problem. This completes the proof.

Problem 11 (Tuymaada 2004). Let a, n be positive integers such that a ≥ lcm(1, 2, · · · , n −

1). Prove that there are pairwise distinct prime numbers p1 , p2 , · · · , pn such that pi | a + i for
1 ≤ i ≤ n.

Solution. Let b = lcm(1, 2, · · · , n − 1), thus a ≥ b. Consider the numbers

a+i
xi = , 1≤i≤n
gcd(a + i, b)
We claim that x1 , x2 , · · · , xn are pairwise relatively prime integers and xi > 1 for all i. Note
that this immediately implies the result, by taking pi to be an arbitrary prime divisor of xi .
To prove the claim, note that xi > 1 is clear, since the equality a + i = gcd(a + i, b) would
force a + 1 ≤ b. Assume now that a prime p divides both xi and x j , for some 1 ≤ i < j ≤ n.
Let k = v p (b). Then
min(v p (a + i), v p (a + j)) ≤ v p ((a + j) − (a + i)) = v p ( j − i) ≤ v p (b) = k
We may assume that v p (a + i) ≤ k, but then
v p (xi ) = v p (a + i) − min(v p (a + i), k) = 0,
 Introduction 11

a contradiction. This completes the proof.

Problem 12 (IMO Shortlist 2011). Let d1 , d2 , . . . , d9 be pairwise distinct integers. Prove

that if x is a sufficiently large integer, then (x + d1 ) (x + d2 ) . . . (x + d9 ) has a prime divisor
greater than 20 .

Solution. Assume the contrary that P(x) has no prime factors greater than 20, we will
show x is bounded.
Let D = ∏1≤i< j≤9 (d j − di ). Observe for all x that gcd(x + di , x + d j ) | d j − di | D. In
particular, for all primes p ≤ 20,

min{v p (x + di ), v p (x + d j )} p (D),

so there is at most one j = 1, . . . , 9 with v p (x + d j ) > v p (D).

But there are eight primes p ≤ 20, so by Pigeonhole for some j = 1, . . . , 9, we have
v p (x + d j ) p (D) for all p, so x + d j ≤ D, implying that x is bounded above by a constant,
which is a contradiction as x tends to infinity.

Problem 13 (APMO 2017). Call a rational number r powerful if r can be expressed in the
pk
form for some relatively prime positive integers p, q and some integer k > 1. Let a, b, c be
q
positive rational numbers such that abc = 1. Suppose there exist positive integers x, y, z such
that ax + by + cz is an integer. Prove that a, b, c are all powerful.

Solution. Fix a prime p and look at ν p ’s. Note ν p (a) + ν p (b) + ν p (c) = 0.

Let p be a prime for which ν p (a) > 0. WLOG ν p (c) < 0; then it follows ν p (b) < 0 too.
Then we conclude yν p (b) = zν p (c), so set ν p (b) = −z0 k and ν p (c) = −y0 k where y0 =
y 0 z
gcd(y,z) and z = gcd(y,z) .

0 < ν p (a) = −ν p (b) − ν p (c) = k · (y0 + z0 ).

Thus, in conclusion, whenever ν p (a) > 0 we have y0 + z0 divides ν p (a).

Problem 14 (India 2019 TST). Show that there do not exist natural numbes a1 , a2 , · · · , a2018
such that the numbers
(a1 )2018 + a2 , (a2 )2018 + a3 , · · · , (a2018 )2018 + a1
are all powers of 5

Solution. Suppose on the contrary that all the given sums are powers of 5. For a
prime p and a natural number n, let v p (n) denote the highest exponent of p dividing n.
 Introduction 12

In what follows, indices are considered modulo 2018.

Suppose that 5 divides ai for some 1 ≤ i ≤ 2018. Then clearly 5 divides a j for all
1 ≤ j ≤ 2018. Let k be such that v5 (ak ) = max{v5 (a1 ), v5 (a2 ). · · · , v5 (a2019 )}. Then
v5 (a2018
k + ak+1 ) = v5 (ak+1 ) and hence a2018
k + ak+1 ≤ ak+1 , a contradiction. This implies
that 5 does not divide ai for any i = 1, 2, · · · , 2018.

Now let bi = a2018 i + ai+1 for i = 1, 2, · · · , 2018. Without loss of generality, as-
sume b1 = min{b1 , b2 , · · · , b2018 }. Let b = b1 . Then since all bi ’s are powers of 5 it follows
that bi ≡ 0 (mod b) for all i = 1, 2, · · · , 2018. Note that a2 ≡ −a2018 1 (mod b). Therefore
2018 2018 2 2018 k
a3 ≡ −a2 ≡ −a1 . Proceeding similarly, ak+1 ≡ −a1 for k = 3, 4, · · · , 2018; in
2018 2018
particular, it follows that b divides a1 + a1 . Since (a1 , b) = (a1 , 5) = 1, we see that
20182018 −1
b divides a1 + 1.

Let d denote the smallest natural number such that ad1 ≡ 1 (mod b). Then d divides
2018 −1
ϕ(b) = 4b/5. Also, since a2018
1 ≡ −1 (mod b) it follows that d is even and that it
divides 2(20182018 − 1). Therefore d divides the quantity gcd(4b/5, 2(20182018 − 1)) = 2,
so d = 2 and therefore b = a2018 + a2 divides a1 + 1, implying a1 = a2 = 1 and thus 5|2,
which is absurd. This completes the proof.

Problem 15 (ELMO 2017 Shortlist). For each integer C > 1 decide whether there exist pair-
wise distinct positive integers a1 , a2 , a3 , ... such that for every k ≥ 1, akk+1 divides Ck a1 a2 ...ak

Solution. The answer is no. Suppose not for a fixed C. Consider any prime p. Then
the problem gives

kν p (ak+1 ) ≤ kν p (C) + ν p (a1 ) + · · · + ν p (ak ). (1.1)

Now we have the following key claim (guessed by small values)

Claim— Let Hn denote the nth harmonic number defined by

1 1 1
Hn = + +···+ .
1 2 n
Then
ν p (an ) − ν p (a1 ) ≤ Hn−1 ν p (C).
Introduction 13

Proof. The proof is just strong induction on n. Firstly, put k = 1 in Equation 1 to

get
ν p (a2 ) − ν p (a1 ) ≤ 1ν p (C),
which serves as the base case since H1 = 1. Now assume the result till some n. Then
putting k = n in Equation 1, we find

nν p (an+1 ) ≤ nν p (C) + ν p (a1 ) + ν p (a2 ) + · · · + ν p (an )

≤ nν p (C) + ν p (a1 ) + (ν p (a1 ) + H1 ν p (C)) + · · · + (ν p (a1 ) + Hn−1 ν p (C))
= nν p (a1 ) + (n + H1 + · · · + Hn−1 ) .

and hence
    
1 1 1 1
ν p (an+1 ) − ν p (a1 ) ≤ n+ +···+ +···+
n 1 1 n−1
  
   
1  1 1 1 1 1 1 1 
= 1 + + + · · · + + · · · +  +
   +···+ +···+ 
n 2 2
| {z } n
| {z } n 1 1 n − 1 
2 n
 
1 1 1 1
= n· +n· +···+n· = Hn .
n 1 2 n

and the induction is complete.

The key hypothesis we need now is that ai are pairwise distinct. We want to try to force
ν p (ai ) to be equal for all primes to get a contradiction. The claim gives ν p (C) = 0 =⇒
ν p (an ) ≤ ν p (a1 ). In particular ν p (am ) is eventually constant. So ignore primes for which
ν p (C) = 0. This means we only have a finite set of prime factors to worry about for the
sequence now.
Now we have the following very famous estimate for HN :

Hn ≤ 1 + log(n + 1) =⇒ Hn ≤ log n + log n2 = 3 log n.

(basically Hn = O(log n)).

So the claim clearly gives ν p (an /a1 ) ≤ A log n for some constant A and all primes p. The
idea now is that if we have bA log xc equals some constant w for x = n, n + 1, . . . , m, then
ν p (ax ) ≤ w + ν p (a1 ) for n ≤ x ≤ m. Also, if we can show w < m − n, then by Pigeonhole
Principle, we would find two i, j such that ν p (ai ) = ν p (a j ). So if the interval [n, m] is large
enough, then this will hold for all primes p (since there are only a finite number of them
by our previous assumption), and we would have ai = a j . So we prove the following:

Claim— For any large k, there exists an interval I of length k such that bA log xc is
constant over I and less than k.
 Introduction 14

Proof. The proof is not as hard as it looks. Firstly, observe that A log x < k ⇐⇒
x < ek/A . Next,  
k
A log(x + k) − A log x = A log 1 + .
x
j k
So even if we pick x = ek/A , for large enough k the above expression will be very
small. Hence we can ensure A log(x + k), A log(x) lie between the same two integers.

Note. In this solution, we have used some estimates for Hn . If you do not know about that,
then you can skip this.

Problem 16 (Fake USAMO 2020). Suppose that C is a positive integer and a1 , a2 , a3 , . . . is

an infinite sequence of positive integers satisfying
q
an+1 = a3n −Can

for all positive integers n. Prove that this sequence must be eventually constant, i.e. there
exists a positive integer N such that aN = aN+1 = aN+2 = . . ..

Solution. We begin by deriving some restrictions on the primes that divide an , for
any n. Suppose that, for some n, p | an but p - C. Then, ν p (a3n − Can ) = ν p (an ), so
ν (a ) ν (a )
ν p (an+1 ) = p 2 n . Repeating this, we find that ν p (an+k ) = p2k n , which is impossible for
sufficiently large k (since ν p (an+k ) must be an integer). Hence, if p | an , we must have
p | C. Additionally, suppose p | an+1 for some n ≥ 1. Since p | C, we have

p | a3n −Can
p | a3n
p | an .

Repeating this, we must have p | a1 . These two claims together imply that, for all k, we
have rad(ak ) = rad(a1 ) | rad(c).
Now, pick p | a1 . Note that

1 1 1
ν p (an+1 ) = ν p (a3n −Can ) ≥ min(3ν p (an ), ν p (C) + ν p (an )) = (ν p (an ) + min(2ν p (an ), ν p (C))),
2 2 2
where equality holds unless ν p (an ) = 12 ν p (C). We will prove that, for some `, ν p (a` ) =
ν p (C). Suppose for some n that ν p (an ) ≤ 21 ν p (C). In this case,

3
ν p (an+1 ) ≥ ν p (an ).
2
Hence, for some j > n, we will have ν p (an ) > 12 ν p (C).
 Lifting the Exponent Lemma (LTE) 15

Now, suppose ν p (C) > ν p (an ) > 12 ν p (C). Then, we have

1
ν p (an+1 ) = (ν p (an ) + ν p (C))
2
=⇒ ν p (C) >ν p (an+1 ) > ν p (an ).

By iterating this, we find that ν p (C) > ν p (an+k ) > ν p (an+k−1 ) > · · · > ν p (an ). As the
ν p (ai ) and ν p (C) are all positive integers, this is impossible for large enough k. Finally, if
ν p (an ) > ν p (C) > 21 ν p (C), we find that

1
ν p (an+1 ) = (ν p (an ) + ν p (C))
2
=⇒ ν p (an ) >ν p (an+1 ) > ν p (C).

By iterating this, we find that ν p (an ) > ν p (an+k ) > ν p (an+k−1 ) > · · · > ν p (C), which is,
again, impossible for large k.
The previous two paragraphs imply that, for each n, we either have ν p (an ) ≤ 21 ν p (C) or
ν p (an ) = ν p (C). As we cannot have ν p (an ) ≤ 12 ν p (C) for all n, it follows that we have
ν p (an ) = ν p (C) for some n. However, if ν p (an ) = ν p (C),

1
ν p (an+1 ) = (ν p (an ) + min(2ν p (an ), ν p (C))) = ν p (an ),
2
implying that the sequence {ν p (ai )}∞
i=1 is eventually constant. It follows by repeating
this argument with every prime p | a1 | C (of which there are only finitely many) that the
sequence {ai } is eventually constant, so we are done.

Note. rad(n) is the largest square-free factor of n.

1.2 Lifting the Exponent Lemma (LTE)

Now that we are familiar with the basic notations of the map v p and also on how to use the
function v p to tackle extremely challenging problems, we will go one step further as we learn
about the basics of the celebrated "Lifting the Exponent Lemma". The lemma, is simple and
not difficult to prove, but it is the heart of the solutions to many of the most challenging
problems in the diverse field of olympiad number theory. In this section, we aim to introduce
to the reader about this beautiful lemma and it’s wonderful applications.

Theorem 1.2.1 (Lifting the Exponent lemma) — Let p be an odd prime and let a, b be
integers not divisible by p such that p | a − b. Then for all n ≥ 1, we have
v p (an − bn ) = v p (a − b) + v p (n)
 Lifting the Exponent Lemma (LTE) 16

Proof. Call a positive integer n ≥ 1 good if it satisfies the above condition. We proceed
with a claim,

Claim— If m and n are good, then mn is good.

Proof. Notice that,

v p (amn − bmn ) = v p ((am )n − (bm )n ) = v p (am − bm ) + v p (n) = v p (a − b) + v p (mn)

and we are done.

It is clear that 1 is good, so it suffices to show that any prime q is good. We divide this
into two cases,
Case 1. If q 6= p
It suffices to show that
aq − bq
= aq−1 + aq−2 b + · · · bq−1
a−b
is not divisible by p. But this is clear, since

aq−1 + aq−2 b + · · · bq−1 ≡ qaq−1 6≡ 0 (mod p)

Case 2. If p = q
We can assume that a = b + pk c for some integer k ≥ 1 and some positive integer c not
divisible by p. Then, the binomial formula yields,
 
p p k+1 p−1 p p−2 2k
a −b = p b c+ b p c + · · · + pkp c p
2

Since p > 2, the numbers 2p b p−2 p2k c, · · · , pkp c p have p-adic valuation greater than k +1,

whence
v p (a p − b p ) = v p (pk+1 b p−1 c) = 1 + k = 1 + v p (a − b)
as desired.

This theorem has an interesting corollary,

Corollary 1.2.2 — Let p be an odd prime and let a, b be integers not divisible by p such
that p | a + b. Then for all odd positive integers n, we have

v p (an + bn ) = v p (n) + v p (a + b)

Now we have seen the case when p is an odd prime, but what about the case when p = 2?
This case is the most interesting, and surprisingly there is a theorem for that as well.
 Lifting the Exponent Lemma (LTE) 17

Theorem 1.2.3 — Let x and y be odd positive integers and let n be an even positive
integer, then  2
x − y2

n n
v2 (x − y ) = v2 + v2 (n)
2

Proof. Write n = 2k a for some integer k ≥ 1 and some odd positive integer a. Then,
we have  k−1 
n n a a a a 2a 2a 2 a 2k−1 a
x − y = (x − y )(x + y )(x + y ) · · · x +y

and since for any c, d ∈ Z, we have c2 + d 2 ≡ 2 (mod 4), the previous relation yields

v2 (xn − yn ) = v2 x2a − y2a + k − 1

x2a −y2a
Finally since a, x, y are odd, it is easy to observe that x2 −y2
= x2(a−1) + · · · + x2(a−1) which
is clearly odd, and this completes the proof.

Now that we are clear with the theory part, let us move on to tackle some concrete and
challenging problems.

Problem 17 (AoPS). Let k be a positive integer.Find all positive integers n such that
3k | 2n − 1
Solution. First, notice that 3 | 2n − 1 then n is even number, n = 2m for some m ∈ N.
Then 3k | 4m − 1. By lifting the exponent Lemma, V3 (4m − 1) = 1 + V3 (m) which gives
V3 (m) ≥ k − 1. So the answer is n = 2 · 3k−1 · l for any l ∈ N

Problem 18 (AoPS). Find all natural numbers k such that k first prime p1 , p2 , . . . , pk then
there are exist 2 numbers a,n satisfy
p1 p2 . . . pk − 1 = an
Solution. Assume that there exists (k, a, n) ∈ Z3+ with n > 1 and k ≥ 2 for which
∏ki=1 pi = an +
1. Since p2 = 3, we have 3 | an + 1, which implies 2 - n and a > 1. Since
gcd ∏ki=1 pi , a = 1, we have a > pk . So we also have pnk < an + 1 = ∏ki=1 pi < pkk which
implise n < k. Since n > 1 is odd, we can take an odd prime divisor q of n. Since q < k,
we must have q | an + 1. Since q | n and q | an + 1, by LTE, we must have q2 | an + 1.
This is clearly impossible. Therefore, k = 1 is the only solution.

Problem 19 (AoPS). Let p > 2013 be a prime. Also let a and b be positive integers such
that p | a + b but p - (a + b)2 . If p2 | a2013 + b2013 , then find the number of positive integers
n ≤ 2013 such that pn | a2013 + b2013 .
 Lifting the Exponent Lemma (LTE) 18

Solution. We
can rewrite the first condition as v p (a + b) = 1. We must also have
v p a2013 + b2013 ≥ 2. Now, if p - a, b, then by Corollary 1.2.2, we have

v p a2013 + b2013 = v p (a + b) + v p (2013) = 1,

a contradiction. Thus p | a, b and this implies that p2013 | a2013 + b2013 and so all values
n ≤ 2013 satisfy pn | a2013 + b2013 and so the answer is 2013.

Problem 20 (2007 Brazil TST). Find all integer solutions to the equation

x7 − 1
= y5 − 1.
x−1

Solution. We proceed with a claim.

x7 −1
Claim— If x is an integer and p is a prime divisor of x−1 = y5 − 1 then we have p ≡ 1
(mod 7) or p = 7.
Proof. p|x7 − 1 and p|x p−1 − 1 (Fermat’s Little Theorem).Let us assume that 7
7 −1
does not divide p − 1.Then gcd(p − 1, 7) = 1,so p|xgcd(p−1,7) − 1 = x − 1,so xx−1 =
6
1 + x + .... + x ≡ 7 (mod p) and hence we get p = 7.This completes the proof of the
lemma.

x7 −1
Let k be a positive divisor of x−1 .Then k ≡ 0 (mod 7) or k ≡ 1 (mod 7).Let us assume
−1 7
that (x, y) is an integer solution of the equation.Then y − 1| xx−1 ⇒ y ≡ 1 (mod 7) or
2 3 4
y ≡ 2 (mod 7)For the first case,1 + y + y + y + y ≡ 5 (mod 7) while in the second case
7 −1
1 + y + y2 + y3 + y4 ≡ 3 (mod 7).This contradicts the fact that a positive divisor of xx−1
must be congruent to 0 or 1 modulo 7.So we have no solutions.

Problem 21 (American Mathematical Monthly). Let a, b, c be positive integers such that

c −bc
c | ac − bc . Show that c | aa−b .

Solution. Let v p (c) = k for some prime p and k ≥ 1. If p - a − b, then we obviously

have
ac − bc
pk |
a−b
Therefore consider p | a − b. Then using LTE for p 6= 2, we have
 c
a − bc

vp = v p (a − b) + v p (c) − v p (a − b) = k
a−b
 Lifting the Exponent Lemma (LTE) 19

When p = 2, we have
 c
a − bc

v2 = v2 (a − b) + v2 (a + b) + v2 (c) − 1 ≥ v2 (c) = k
a−b

and the problem is solved in all cases. This completes the proof.

Problem 22. Let n be a square-free integer. Show that there is no pair of coprime positive
integers (x, y) such that
(x + y)3 | (xn + yn )

Solution. Assume (x + y)3 | (xn + yn ) with gcd(x, y) = 1. We will derive a contradiction.

First, suppose n is even. If there is an odd prime p | (x + y), then xn + yn ≡ xn + (−x)n ≡
2xn mod p, so p | x, so p | y, contradiction. Since x and y are positive, the only possible
way that there is no odd prime p dividing x + y is if x + y is a power of 2. In this case, x
and y are both odd since they are coprime, so since n is even xn and yn are both 1 mod 8,
it follows that v2 (xn + yn ) = 1, but v2 (x + y)3 ≥ 3, so again we get a contradiction.

Now suppose n is odd. If there is an odd prime p | (x + y), then 3v p (x + y) ≤ v p (xn + yn ).

Then LTE gives

3v p (x + y) ≤ v p (xn + yn ) = v p (x + y) + v p (n) ≤ v p (x + y) + 1

since n is square-free. Simplifying, we get v p (x + y) ≤ 21 , which is impossible since p |

(x + y). As above, the only remaining case is when x + y is a power of 2 . But in this
case, v2 (xn + yn ) = v2 (x + y) if n is odd, because x and y are odd and the expansion of

xn + yn
= xn−1 − xn−2 y + · · · − xyn−2 + yn−1
x+y

has an odd number of terms, all of which are odd. So it is impossible for (x + y)3 to divide
xn + yn , since the power of 2 on the left exceeds the power of 2 on the right.

Problem 23. Suppose a and b are positive real numbers such that a − b, a2 − b2 , a3 − b3 , . . .
are all positive integers. Show that a and b must be positive integers.

−b 2 2
Solution. Since a − b ∈ Z and a2 − b2 ∈ Z, a + b = aa−b ∈ Q. But then a = 12 (a − b) +
1 1 1 x
2 (a + b) and b = 2 (a + b) − 2 (a − b) are rational numbers as well. Now, write a = z and
y
b = z as quotients of positive integers, with a common denominator. Choose z as small
as possible. Then the conditions of the problem imply that

zn | (xn − yn ) for all n .

Suppose p is a prime dividing z. Note z | (x − y) so p | (x − y). If p | x, then p | y as well,

 Lifting the Exponent Lemma (LTE) 20

z y
but that violates the choice of z : we could write a = pp , b = p
p to get a smaller common
p p
denominator. So p - x, y and we are set up to apply LTE. If p is odd, then

n ≤ v p (zn ) = v p (xn − yn ) = v p (x − y) + v p (n).

Taking p to both sides gives

pn ≤ (x − y)n
pn
≤ (x − y)
n
but this is impossible since the left side goes to infinity as n → ∞, and the right side is a
constant independent of n. If p = 2, we get

n ≤ v2 (zn ) = v2 (xn − yn ) = v2 (x − y) + v2 (n) + v2 (x + y) − 1,

so
2n+1
≤ (x − y)(x + y)
n
and we get a similar contradiction. The conclusion is that there is no prime p dividing z.
So z = 1 and a and b are both positive integers.

Problem 24 (Russia 1996). Find all positive integers n for which there exist positive integers
x, y and k such that gcd(x, y) = 1 and 3n = xk + yk .

Solution. Note that k must be odd (why?). Now, let p be a prime dividing x+y, clearly p
is odd. Then by corollary 1.2.2, we have that v p (3n ) = v p (xk + yk ) = v p (k) + v p (x + y) > 0,
as v p (x + y) ≥ 1 > 0. Thus, p | 3k , implying that p = 3. Thus x + y = 3m for some
positive integer m. Note that n = v3 (k) + m. We proceed with two cases,

Case 1. If m > 1.
We can prove by induction that 3a ≥ a + 2 for all integers a ≥ 1, and so we have
v3 (k) ≤ k − 2 (if v3 (k) = a, then v3 (k) + 2 = a + 2 ≤ 3a ≤ k). Let M = max(x, y). Since
x + y = 3m ≥ 9, we have M ≥ 5. Then
x + y k−1 1 m k−1
xk + yk ≥ M k = M · M k−1 ≥ ·5 = 3 ·5 > 3m · 5k−2 ≥ 3m+k−2 ≥ 3m+v3 (k) = 3n
2 2
, a contradiction.

Case 2. If m = 1.
Then x + y = 3, so x = 1 and y = 2 (or x = 2 and y = 1). Thus 31+v3 (k) = 1 + 2k . But
note that 3v3 (k) | k, so 3v3 (k) ≤ k. Therefore
1 + 2k = 31+v3 (k) = 3 · 3v3 (k) ≤ 3k =⇒ 2k + 1 ≤ 3k
and one can easily see that the only odd value of k > 1 satisfying the above inequality is
k = 3. Thus, (x, y, n, k) = {(1, 2, 2, 3), (2, 1, 2, 3)}, implying that the only value is n = 2.
 Lifting the Exponent Lemma (LTE) 21

Problem 25. (Iran 2008 Round 2) Let a be a natural number. Suppose that 4 (an + 1) is a
perfect cube for every natural number n. Prove that a = 1

Solution. If an odd prime p divides an + 1 for some n, then v p (an + 1) must be divisible
by 3 , since gcd(p, 4) = 1. This is the key insight.
Now, we are clearly motivated to try LTE by looking at v p (an + 1) . So, we want the 3
conditions. By assumption, p > 2. Also, p - a . We just want p | a + 1 and n odd. So
let’s start by this assumption. Pick an odd prime p divisor of a + 1, if it exists . Then by
Fermat’s Little Theorem, p|a + 1|a pk + 1 for all k. So, by LTE
 
pk
v p a + 1 = v p (a + 1) + v p (k) + 1 ∀ odd k

We know this is divisible by 3 for all odd k (why do we need odd k? ). However, since
v p (a + 1) + 1 is fixed, hence we can choose (odd) k such that v p (a + 1) + v p (k) + 1 6= 0
( mod 3), which is a contradiction. Hence, our assumption that a + 1 has an odd prime
factor was false. So a + 1 can’t have an odd prime factor.
Write a+1 = 2k . Here’s the clever trick now: since gcd a2 + 1, a + 1 = gcd(a+1, 2) = 2,

hence a2 +1 will have an odd prime factor p if k > 1 . So, you can repeat the process above
with a2 instead of a and still get a contradiction (convince yourself that this argument
works). Hence, k = 1, meaning a + 1 = 2, i.e. a = 1, as needed.

Problem 26 (AoPS). Find all f : N → N such that:

• There exists M ∈ N such that f (n) 6= 1 for all n ≥ M,

n−1 n−1
• f (a)n | f (a + b)a − f (b)a holds for all a, b, n ∈ N.

Solution. We proceed with a claim.

Claim— For any natural numbers a, f is either a-periodic (i.e. f (a + b) = f (b) for all
b ∈ N) or f (a)|a.
Proof. Suppose that f (a + b) 6= f (b) for some b ∈ N. Consider any prime number
p. Plugging in n yields f (a)| f (a + b) − f (b). Thus, by Lifting The Exponent Lemma,
if p is odd,
 n−1 n−1

v p ( f (a)n ) ≤ v p f (a + b)a − f (b)a
nv p ( f (a)) ≤ v p ( f (a + b) − f (b)) + (n − 1)v p (a)

If p = 2, one would obtain nv2 ( f (a)) ≤ v2 ( f (a + b)2 − f (b)2 ) + (n − 1)v p (a) − 1.

Either way, v p ( f (a)) > v p (a) yields a contradiction for some n big enough, so in fact
we have v p ( f (a)) ≤ v p (a) for all p prime, and thus f (a)|a.
Otherwise, f (a + b) = f (b) for all b ∈ N and f would be a-periodic.
 Zsigmondy’s Theorem 22

Returning back to the main problem, the lemma implies that if f (1) 6= 1, then f is 1-
periodic and thus constant. So, now we assume f is non-constant, and thus f (1) = 1.
By the first point, f cannot be periodic; otherwise there exists n ≥ M such that f (n) = 1.
Now, fix a positive integer a, and let p be a prime number with p > max{M, a}. Then,
since f (p) 6= 1, we have f (p) = p. Hence,

p| f (p + a) − f (a)

But 0 < f (p + a) ≤ p + a < 2p and 0 < f (a) ≤ a < p, so −p < f (p + a) − f (a) < 2p and
thus we get either f (p + a) = f (a) or f (p + a) = p + f (a). However, if f (p + a) = f (a),
then f (p+a) divides both p+a and a. But gcd(p+a, a) = gcd(p, a) = 1, so f (p+a) = 1.
But p + a ≥ M; a contradiction.
Hence, f (p + a) = p + f (a), so p + f (a)|p + a. Since p + f (a) > p+a
2 , then p + f (a) =
p + a and thus f (a) = a.
Since this holds for all a ∈ N, we conclude that f is the identity function on N.

1.3 Zsigmondy’s Theorem

This is the last section of this chapter. To make this chapter firm, we employ one of the
strongest techniques in Olympiad Number Theory, the celebrated Zsigmondy’s Theorem. This
theorem has cracked numerous amount of challenging Olympiad problems around the world,
such as USA(J)MO, IMO, Bulgaria, Balkan, China, India, and many more. This technique lies
in the heart in one of the author. We hope you will be able to learn how and when to employ
this new technique, though we haven’t included the proof.

Before the main theorem, we state what a primitive prime factor is.

Definition— We say that p is a primitive prime factor of an − bn , where a, b, n ∈ N if p is a

prime factor of an − bn and for all 1 ≤ k < n, p - ak − bk .

Theorem 1.3.1 (Zsigmondy) — Let a and b be relatively prime positive integers. Then,
an − bn always has a primitive prime factor for n ∈ N with the following exceptions,

• 26 − 16

• n = 2 and a + b is a power of 2

We now discuss a second variant of Zsigmondy’s.

Theorem 1.3.2 (Zsigmondy’s Variant) — Let a and b be relatively prime positive integers.
Then, there exists a primitive prime factor of an + bn , where n ∈ N with the following
 Zsigmondy’s Theorem 23

exception,

• 23 + 13
Note. The proof of this uses Zsigmondy, we hope the reader can prove this.

Now that we are clear with the basics, we move on to tackle some concrete problems.

Problem 27 (Poland 2010). Let p and q be prime numbers with p > q > 2. Prove that
2 pq − 1 has at least three prime factors.

Solution. First, note that 2 p − 1 and 2q − 1 are divisors of 2 pq − 1, so we have at least

two prime factors with us. Now, since p > q > 2, by Zsigmondy, we have that 2 pq − 1
has a primitive prime factor, and hence we have at least three prime factors in addition,
completing the proof.

Problem 28 (IMO 2000 Shortlist). Find all triples (a, m, n) of positive integers that satisfy
the divisibility condition
am + 1 | (a + 1)n

Solution. If a = 1 then the divisibility condition obviously work. Assume now that a ≥ 2.
If m = 1 then the divisibility condition obviously work. Assume now that a ≥ 2, m ≥ 2. If
the two conditions a = 2, m = 3 are not both true then by Zsigmondy’s there must exist a
prime factor p of am + 1 which does not divide a + 1 (and of course so does not (a + 1)n ).
Hence there is no solution in this case. It suffices for us to consider the single case a = 2,
m = 3, in which only all n ≥ 2 satisfy the divisibility condition. Therefore the solutions are
only (1, m, n), (a, 1, n), (2, 3, k) where k ≥ 2.

Problem 29. Find all natural numbers n, k, l, m with l > 1 such that
(1 + nk )l = 1 + nm
Solution. First, note that k < m. Next Zsigmondy guarantees the existence of a primitive
prime factor of nm + 1 except for n = 2 and m = 3. If n and m are not the respective
values given, then nm + 1 has a prime divisor not dividing nk + 1, a contradiction. If n = 2
and m = 3, we find that (k, l, m, n) = (1, 2, 2, 3) is the only solution.

Problem 30 (AoPS). Let a and b be positive integers such that an + bn | cn holds for all
n > 1, then show that a = b.

Solution. Without loss of generality, let gcd(a, b) = 1 because we can just divide both
sides of the divisibility by gcd(a, b) if this is not true. By Zsigmondy’s theorem, for n ≥ 3
 Zsigmondy’s Theorem 24

and a 6= b we must have that an+1 + bn+1 has a prime factor that didn’t appear for ak + bk
and 1 ≤ k ≤ n. However, the number of prime factors of c is finite, so sooner or later
we will run out of new prime factors of ak + bk , contradiction. The only other option is
a = b, hence proved.

Problem 31 (Baltic Way 2012). Let d(n) denote the number of positive divisors of n. Find
all triples (n, k, p), where n and k are positive integers and p is a prime number, such that
nd(n) − 1 = pk .
Solution. We split the problem into two cases,

Case 1. n = 2
This immediately gives p = 3 and k = 1

Case 2. n >= 3.
f d(n) 6= 2, by Zsigmondy’s theorem, there exists a prime q such that q|nd(n) − 1, q - n − 1.
Since n − 1|nd(n) − 1, this is absurd. Hence d(n) = 2. Then (n + 1)(n − 1) = pk . For
s > t ≥ 0,
n + 1 = ps


n − 1 = pt
which implies that 2 = pt (ps−t − 1).If t = 0,then p = 3, s = 1, n = 2 which is absurd. Thus
t ≥ 1 and p = 2,t = 1, s = 2, n = 3, k = 3. which satisfies the condition.

Problem 32 (Japan MO 2011). Find all of quintuple of positive integers (a, n, p, q, r) such
that an − 1 = (a p − 1) (aq − 1) (ar − 1).

Solution. We split the problem into two cases.

Case 1. a = 1
(1, n, p, q, r) satisfies the condition.
´Case 2. a ≥ 2
Then, n ≥ p, q, r. We break this into two subcases.

Case 2.1 n = max{p, q, r}

Without loss of generality, let n = p. Obviously a = 2 and q = r = 1. By
symmetry,(2, n, n, 1, 1), (2, n, 1, n, 1), (2, n, 1, 1, n) satisfy the condition.

Case 2.2 n > max{p, q, r}

Then, we have n ≥ 2. We break this further into two subcases.

Case 2.2.1 n = 2
Thus, p = q = r = 1 and (a2 − 1) = (a − 1)3 , which implies to and is implied by a = 0, 3.
Zsigmondy’s Theorem 25

Then a = 3, and so (3, 2, 1, 1, 1) satisfies the condition.

Case 2.2.2 n ≥ 3
If not (a, n) = (2, 6), by Zsigmondy’s theorem there is prime number p0 such
that p0 |an − 1, p0 - a p − 1, p0 - aq − 1, p0 - ar − 1 which is absurd. Hence
2 p q r
(a, n) = (2, 6) and 3 7 = (2 − 1)(2 − 1)(2 − 1).By 6 > p, q, r,then (p, q, r) =
(3, 2, 2), (2, 3, 2), (2, 2, 3).(2, 6, 3, 2, 2), (2, 6, 2, 3, 2), (2, 6, 2, 2, 3) satisfy the condition.

From the above cases, our final answer is

(a, b, p, q, r) = (1, n, p, q, r), (3, 2, 1, 1, 1), (2, 6, 2, 2, 3), (2, 6, 2, 3, 2), (2, 6, 3, 2, 2)
 The p-adic valuation of n! CHAPTER 2. LEGENDRE’S FORMULA 26

Chapter 2

Legendre’s Formula

In this chapter, we will discuss Legendre’s formula, which finds the p-adic valuation of n!. After
fully understanding the Legendre’s formula, we will move on to some beautiful applications of
Legendre such as Lucas, Kummer and many other beautiful lemmas that are a rare gem in
Olympiad Number Theory.

2.1 The p-adic valuation of n!

In this section, we aim to find the exact formula of v p (n!) for any prime p. Now, if you note
that the number of multiples of p in the first n consecutive naturals is just b np c, implying that
is the power of p in n!. But what about multiples of p that are multiples of p2 or p3 ? This
means that the answer is definitely not b np c, so there is a slight catch to evaluate the number
v p (n!), or the exponent of p in the prime factorisation of n! . The proof of Legendre uses just
this basic fact, but it’s applications are really diverse.

Theorem 2.1.1 (Legendre) — For all primes p and positive integers n, we have
∞  
n
v p (n!) = ∑ i
i=1 p

Proof. By basic properties of p-adic valuations, note that

v p (n!) = v p (1) + v p (2) + · · · v p (n)
As pointed out in the introduction of this chapter, there are b pni c multiples of pi in n!.
Since the number of multiples of p but not p2 contribute 1 to the sum, the multiples of
p2 but not p3 contribute 2 to the sum,· · · we have that
           
n n n n n n
v p (n!) = − 2 +2 − + 3 − +···
p p p2 p2 p3 p4
 The p-adic valuation of n! 27

which telescopes to the desired formula.

We shall now move on to some concrete examples.

Problem 33 (China 2004 TST). Let m1 , m2 ,· · · , mr and n1 , n2 ,· · · , ns be positive integers

such that for any integer d > 1, there are more or equal multiples of d in m1 , m2 ,· · · , mr than
those of n1 , n2 ,· · · , ns . Prove that n1 n2 · · · ns | m1 m2 · · · mr .

Solution. Let Md and Nd be the number of multiples of d in m1 , m2 ,· · · , mr and n1 ,

n2 ,· · · , ns respectively. By hypothesis, we have Md ≥ Nd for all d > 1. Therefore, for all
primes p, we have

v p (m1 m2 · · · mr ) = M p + M p2 + · · · + M pn + · · · ≥ N p + N p2 + · · · + N pn + · · · = v p (n1 n2 · · · ns )

where the above equation follows from equivalent arguments as in the proof of Legendre’s
Formula.

Problem 34 (USAMO 2016). Prove that for any positive integer k,

k−1
j!
(k2 )! · ∏
j=0 ( j + k)!

is an integer.
1!···(k−1)!
Solution. We need to prove that (k2 )! · k!···(2k−1)! ∈ Z. Applying Legendre’s formula, it
suffices to prove
k−1    2  k−1  
k+i k i
∑ pi ≤ pi + ∑ pi ,
i=0 i=0
for any p < 2k prime. Since bac + 1 > a so it’s suffices to prove that

k2 k−1
   
k+ j j
>∑ − i .
pi j=0 p i p

We prove this by induction. Assume that it’s true for k, we need to prove that it’s also
true for k + 1, or
k 
(k + 1)2
  
k+1+ j j
i
>∑ i
− i .
p j=0 p p
 The p-adic valuation of n! 28

Indeed, using ba + bc − 1 ≤ bac + bbc ≤ ba + bc and the induction hypothesis we have

(k + 1)2 k2 2k + 1
= i+ ,
pi p pi
k−1    
k+ j j 2k + 1
≥∑ i
− i +1+ ,
j=0 p p pi
k             
k+1+ j j 2k + 1 2k + 1 k 2k
=∑ − i + − + 2 i − i +1 ,
j=0 pi p pi pi p p
k    
k+1+ j j
≥∑ i
− i .
j=0 p p

We are done.

Problem 35 (RMM 2009). For ai ∈ Z+ , i = 1, . . . , k, and n = ∑ki=1 ai , let d = gcd(a1 , . . . , ak )

denote the greatest common divisor of a1 , . . . , ak . Prove that
d n!
·
n k
∏ (ai !)
i=1
is an integer.

Solution. The key idea is to note that the to prove that can be rewritten as
 
n n
|
d a1 , a2 , · · · , ak
Let p be a prime divisor of the LHS. It therefore suffices to show that for each 1 ≤ i ≤ k
k
v p (n) − v p (ai ) ≤ v p (n!) − ∑ v p (al !)
l=1

By Legendre’s formula, we have each of the following identities,

∞  
n
v p (n!) = ∑ j
j=1 p
v p (n) = v p (n!) − v p ((n − 1)!)
∞    
n n−1
=∑ −
j=1 pj pj

Thus, it suffices to show that

∞         ∞   $ k %!
n n−1 ai ai − 1 n al
∑ pj − pj − pj + pj ≤ ∑ pj
− ∑ j
j=1 j=1 l=1 p
 The p-adic valuation of n! 29

It remains to show that for all j ∈ N and 1 ≤ i ≤ k

          $ k %
n n−1 ai ai − 1 n al
− − + ≤ − ∑ j
pj pj pj pj pj l=1 p

which reduces to      
n−1 al ai − 1
≥∑ +
pj l6=i pj pj
But this follows from the fact that for any reals a and b, we have

ba + bc ≥ bac + bbc

Details are left to the reader. This completes the proof.

We now move on to an important theorem that can be used to solve many problems using
p-adic valuations that are inequality based. But the proof of this is beyond the scope of this
article.

Theorem 2.1.2 — For all n > 1 and primes p, we have that

n n
− 1 < v p (n!) <
p p−1

We show one usage of this.

Problem 36 (MEMO 2015). Find all pairs (a, b) of positive integers such that

ab + ba = a! + b!

Solution. Without loss of generality, let a ≤ b. If a = 1, the equation becomes b! = b,

so (a, b) = (1, 1), (1, 2), (2, 1). Suppose now that a ≥ 2. Then, ab − b! = ba − a! ≥
aa − a! > 0, thus b! > ab . On the other hand, by AM-GM Inequality, we have that
 b  b
b(b + 1) b+1
b! = 1 · 2 · 3 · · · b ≤ =
2b 2

which implies that 2a < b + 1. Thus, b ≥ 2a.

Let p be a prime divisor of a. Then, p | a! + b! and p | ab and hence p | b. Therefore,
v p (ab + ba ) ≥ a. On the other hand, since b ≥ 2a, we have that p | (a + 1) · (a + 2) · · · b,
hence
v p (a! + b!) = v p (a!) + v p (1 + (a + 1) · (a + 2) · · · b) < a
where the last inequality follows from Theorem 2.1.2. But this gives a < a, a contradiction.
Thus the only solutions are (a, b) = (1, 1), (1, 2), (2, 1).
 Introduction and LTE CHAPTER 3. PRACTICE PROBLEMS 30

Chapter 3

Practice Problems

We have now come to the end of the handout, and we therefore conclude with a set of practice
problems.

3.1 Introduction and LTE

Exercise 3.1.1. Prove that gcd(a, b) × lcm(a, b) = a × b

Exercise 3.1.2. Let a and b be integers such that

a | b2 | a3 | b4 · · ·

Show that a | b.

Exercise 3.1.3. Prove that

1 1
1+ +···+
3 2n − 1
is not an integer.

Exercise 3.1.4. Let a, b, and c be integers such that

ab ac bc
+ +
c b a
is an integer. Prove that each of the numbers
ab ac bc
, , and
c b a
is an integer.

Exercise 3.1.5 (Polish Junior). Let a and b be positive odd integers such that ab ba is a
perfect square. Show that ab is a perfect square.
 Introduction and LTE 31

Exercise 3.1.6. Find all positive integers a and b such that a + b3 b + a3 is a power of

3.
Exercise 3.1.7 (Iran TST 2013). Find all arithmetic progressions a1 , a2 , · · · of positive integers
for which there is an integer N > 1 such that for all k ≥ 1,

a1 a2 · · · ak | aN aN+1 · · · aN+k

Exercise 3.1.8 (Canada). Find all positive integers n such that 2n−1 | n!
Exercise 3.1.9 (2019 USA TSTST). Let f : Z → {1, 2, . . . , 10100 } be a function satisfying

gcd( f (x), f (y)) = gcd( f (x), x − y)

for all integers x and y. Show that there exist positive integers m and n such that f (x) =
gcd(m + x, n) for all integers x.
Exercise 3.1.10 (RMM 2018). Let a, b, c, d be positive integers such that ad = 6 bc and
gcd(a, b, c, d) = 1. Prove that as n runs through the positive integers, the value gcd(an +
b, cn + d) may achieve, form the set of all positive divisors of some integer.
Exercise 3.1.11 (China 2016 TST). Let c, d ≥ 2 be naturals. Let {an } be the sequence
satisfying a1 = c, an+1 = adn + c for n = 1, 2, · · · . Prove that for any n ≥ 2, there exists a prime
number p such that p|an and p 6 |ai for i = 1, 2, · · · n − 1.
Exercise 3.1.12 (USAMO 2009). Let s1 , s2 , s3 , . . . be an infinite, nonconstant sequence of
rational numbers, meaning it is not the case that s1 = s2 = s3 = . . . . Suppose that t1 ,t2 ,t3 , . . . is
also an infinite, nonconstant sequence of rational numbers with the property that (si − s j )(ti −
t j ) is an integer for all i and j. Prove that there exists a rational number r such that (si − s j )r
and (ti − t j )/r are integers for all i and j.
Exercise 3.1.13 (Saint Petersburg 2020). The sequence an is given as

a1 = 1, a2 = 2 and an+2 = an (an+1 + 1) ∀n ≥ 1

Prove that aan is divisible by (an )n for n ≥ 100.

Exercise 3.1.14 (2012 ARMO). For a positive integer n define Sn = 1! + 2! + . . . + n!. Prove
that there exists an integer n such that Sn has a prime divisor greater than 102012 .
Exercise 3.1.15. Call a sequence of positive integers {an } good if for any distinct positive
integers m, n, one has

gcd(m, n) | a2m + a2n and gcd(am , an ) | m2 + n2 .

Call a positive integer a to be k-good if there exists a good sequence such that ak = a. Does
there exists a k such that there are exactly 2019 k-good positive integers?
Exercise 3.1.16 (BMO 2018). Find all primes p and q such that 3pq−1 + 1 divides 11 p + 17 p
Exercise 3.1.17. Let x, y be non-negative

n integers.

n Prove that there exist finitely many
non-negative integers n such that x + 21 + y + 12 is an integer.
 Legendre’s Formula 32

Exercise 3.1.18 (2013 JBMO TST). Find all positive integers x, y, z with z odd, which satisfy
the equation:

2018x = 100y + 1918z

Exercise 3.1.19 (2010 Indonesia TST). Let n be a positive
√ integer with n = p2010 q2010 for
two odd primes p and q. Show that there exist exactly 2010 n positive integers x ≤ n such that
p2010 |x p − 1 and q2010 |xq − 1.

3.2 Zsigmondy’s Theorem

Exercise 3.2.1 (2017 Japan TST). Find all positive integers k such that there exist positive
integer sequences a1 , a2 , . . . and r1 , r2 , . . . satisfying the following conditions: - a1 < a2 < a3 <
. . . - ak1 + ak2 + . . . + akn = (a1 + a2 + . . . + an )rn holds for all positive integers n
Exercise 3.2.2. Find all pairs of natural numbers (m, n) for which 2m 3n + 1 is the square of
some integer.
Exercise 3.2.3. Let p1 , p2 , . . . , pn be distinct primes greater than 3 . Show that 2 p1 p2 ···p3 + 1
has at least 4n divisors.
Exercise 3.2.4. If an + bn | cn , for all n , then prove that a = b.

3.3 Legendre’s Formula

Exercise 3.3.1 (Saint Petersburg 2007). Find all positive integers n and k for which
1n + 2n + · · · + nn = k!
Exercise 3.3.2 (AMM). Let n ≥ 1 be an integer. Prove that
     
n n n
(n + 1) lcm , ,··· , = lcm(1, 2, · · · , n + 1)
0 1 n
Exercise 3.3.3 (Russia 2012). Prove that there is a positive integer n such that 1! + 2! +
· · · + n! has a prime factor greater than 102012
Exercise 3.3.4 (2007 Romania TST). Solve over the positive integers, the equation
x2007 − y2007 = x! − y!
Exercise 3.3.5 (Mathematical Reflections). Define a sequence (an )n≥1 by a1 = 1 and an+1 =
2n (2an − 1). Prove that n! | an for all n ≥ 1.
 Legendre’s Formula 33

References

[1] Number Theory Concepts and Problems

[2] Art of Problem Solving

[3] Problems from around the world

[4] Blogs on AoPS