Zsigmondy’s Theorem

Bart Michels
February 4, 2014∗

Zsigmondy’s theorem is a by few known theorem that often proves useful in various num-
ber theory problems. In this article we give an elementary proof of Zsigmondy’s theorem.

Zsigmondy’s theorem. Let a, b ∈ N such that gcd(a, b) = 1 and n ∈ N, n > 1. There

exists a prime divisor of an − bn that does not divide ak − bk for all k ∈ {1, 2, . . . , n − 1},
except in the following cases:
• 26 − 16 ,
• n = 2 and a + b is a power of 2.
Such a prime divisor is called a primitive prime divisor of an − bn . Note that 2 can never
be a primitive prime divisor.

The theorem was discovered by Zsigmondy in 1892 and independently rediscovered by

Birkhoff and Vandiver in 1904. The special case where b = 1 was discovered earlier by
Bang in 1886.
The proof we present is mainly a reformulation of Birkhoff and Vandivers proof, which
was published in 1904, see [1]. [1, Theorem 1] is nowadays, among Olympiad enthousiasts,
known as a case of the Lifting The Exponent Lemma. Here we present this Lemma as
Lemma 5, for a proof we refer to [4]. We give a shorter proof of [1, Theorem 5], using
some properties of cyclotomic polynomials. The most important properties are restated
here, a more detailed version with proofs is to be found in [2]. Case 3 in the third part
of the proof given here is a generalisation of its source of inspiration, namely [3, Key
Lemma].

1 Prerequisites
Before proving the main theorem we present some elementary properties of cyclotomic
polynomials. The proofs can be found in [2].
Let Φn (x) denote the n-th cyclotomic polynomial.
Theorem 1. Let p be a prime number. If the polyomial xn − 1 has a double root modulo
p, that is, there exists an integer a and a polynomial f (x) ∈ Z[x] for which

xn − 1 ≡ (x − a)2 f (x) (mod p),

then p | n.
∗
Modified december 1st, 2014

1
Theorem 2. If n is a positive integer, then
Y
xn − 1 = Φd (x) (1)
d|n

and Y n
Φn (x) = (x d − 1)µ(d) . (2)
d|n

Here a negative exponent in the right hand side of (2) has to be interpreted as a division
of polynomials.

Theorem 3. Let p be a prime number and n, k be positive integers. Then

 k
Φn (xp )
 if p | n
p k
Φpk n (x) = Φn (x )
 if p - n.
Φn (xpk−1 )


k
In particular we have that Φpk n (a) | Φn (ap ) for all a ∈ Z.

Theorem 4. Let n be a positive integer and a be any integer. Then every prime divisor
p of Φn (a) either satisfies p ≡ 1 (mod n) or p | n.

There are three more Lemmas that will be useful.

Lemma 5. Let x and y be integers, let n be a positive integer, and let p be an odd prime
such that p | x − y and none of x and y is divisible by p. Then

vp (xn − y n ) = vp (x − y) + vp (n).

Here vp (a) denotes the highest integer exponent k such that pk | a. We also write pk k a.
We will refer to this as the Lifting The Exponent Lemma.

Lemma 6. Let p be prime, n = pα q ∈ Z such that p - q. The integer zeroes of Φn modulo

p have order q modulo p.

Proof.
From p | Φn (a) we certainly have p | an − 1 ≡ aq − 1, so k = ordp (a) exists and k | q.
α
Because (theorem 3) Φn (a) | Φq (ap ) ≡ Φq (a) (mod p) we have that p | Φq (a).
If k < q there would be a divisor d | k for which p | ΦQd (a) (a consequence of (1)). As
q
d | q and d < q this means the polynomial x − 1 = r|q Φr (x) has a double root, a,
modulo p due to a factor Φd (x)Φq (x). From theorem 1 we would obtain that p | q, which
is impossible. Therefore k = q. 

Lemma 7. If n is a positive integer and x > 1 is a real number, then

(x − 1)ϕ(n) 6 Φn (x) < (x + 1)ϕ(n) ,

where the first inequality becomes an equality only if n = 2.

2
Proof.
From the triangle inequality for complex numbers we have x − 1 6 |x − ζ| 6 x + 1 for
any complex number ζ with |ζ| = 1. The first inequality is strict unless ζ = 1, and the
second is strict unless ζ = −1. Applying this we obtain
Y
(x − 1)ϕ(n) 6 |x − ζ| < (x + 1)ϕ(n) ,
ζ n =1
ord(ζ)=n

with equality only if ϕ(n) = 1, that is, n = 2. Note that the second inequality is always
strict, because |x − 1| < |x + 1|. The product in the middle is, by definition |Φn (x)|. If
x > 1 then from (2) we have Φn (x) > 0, hence |Φn (x)| = Φn (x). 

We are ready to prove Zsigmondy’s theorem.

2 Proof of Zsigmondy’s theorem

Fix two coprime positive integers a and b with a > b.
It is sufficient to prove that an − bn has a prime divisor that does not divide ak − bk for
all positive divisors k | n. Indeed, if p | an − bn , c is an inverse of b modulo p and k is
the smallest integer such that p | ak − bk , then k = ordp (ac) has to be a divisor of n, as
(ac)n ≡ 1 (mod p).

1. Connection to cyclotomic polynomials

We define zn = an − bn and Y
Ψn = z nd µ(d) . (3)
d|n

a n



Because zn = bn b
− 1 , from (1) and (2) we have that
a
ϕ(n)
Ψn = b Φn (4)
b
and Y
zn = Ψd . (5)
d|n

If zn = pa11 · · · par r where ps1 , . . . , pst are the primitive prime divisors of zn , we set
a a
Pn = ps1s1 · · · pstst .

From (4) we have Ψn ∈ Z and from (3) it follows that Pn | Ψn , because the only zk for
which gcd(Pn , zk ) > 1 is zn , by definition of Pn . Let Ψn = λn Pn . We will prove that
Pn > 1 in the cases Zsigmondy’s theorem does not exclude.

2. An upper bound on λn
From (5) it follows that Ψn | zznd for every positive divisor d | n with d < n.
Note that gcd(λn , Pn ) = 1, because λn Pn = Ψn | zn and by definition Pn contains all
primitive divisors of zn , so λn can not be a multiple of a prime which divides Pn .
Let p be a prime divisor of Ψn such that p | λn , so p is not primitive. We will prove that
p | n. Let d < n such that p | zd .

3
If p = 2, then from theorem 4 we have 2 | n, at least if n > 1. Suppose p is odd. If p - n
then by the Lifting The Exponent Lemma, vp (zn ) = vp (zd ) so p - zznd , a contradiction to
Ψn | zznd . Hence rad(λn ) | n.
Suppose λn > 1. If p is a prime divisor of λn with pα k n and n = pα q, then from theorem
3 we have
α α
p | Ψn | Ψq (ap , bp ) ≡ Ψq (mod p),
where more generally we denote
 
ϕ(n) x
Ψn (x, y) = y Φn .
y

This means if p is a prime divisor of λn , then p | Ψq . From theorem 4 we obtain that

p ≡ 1 (mod q), because p - q by our assumption. So p > q = pnα .
If r is another prime divisor of n, then r | q, so r 6 q < p. This means p is uniquely
determined as the largest prime divisor of n.
Therefore, set λn = pβ . We will prove that β = 1 if n > 2, and treat the case n = 2
seperately.

If n = 2, a2 − b2 obviously has a primitive prime divisor (any odd prime dividing a + b)

unless a + b is a power of 2, an exception mentioned in the theorem.
n n
If p = 2 we have that n is a power of 2. Then Ψn = a 2 + b 2 , a and b odd. Modulo 4 this
is congruent to 2, which implies β = 1.
Suppose p > 2. Let d | n such that p | zd . Let c be an inverse of b modulo p, then p | Ψn
and thus p | Φ(ac), so by lemma 6, ordp (ac) = q. So certainly we should have q | d.
Now from (3) we have β = vp (Ψn ) = vp (zn ) − vp (z np ), because the only factors that do
not vanish due to the exponent µ(d) and contain a factor p are zn and z np . By the Lifting
The Exponent Lemma, β = 1.

3. A lower bound on Pn
In this part of the proof we exploit the result of Lemma 7. We consider three cases.

Case 1: λn = 1
If λn = 1, then Pn = Ψn > (a − b)ϕ(n) > 1. The inequality is strict unless n = 2 and
a − b = 1, but then Zsigmondy’s theorem is trivially true. 

Case 2: λn = p and a − b > 1

p−1
In this case Pn = p1 Ψn > p1 (a − b)ϕ(n) > 2 p > 1. Again the inequality is strict unless
a − b = 2 and n = 2, which has already been treated. 

Case 3: λn = p and a − b = 1
Suppose the inequality Pn > 1 is not strict, so Ψn = p. This will eventually give us the
only counterexample that’s left, being n = 6, a = 2.
From p | zn it follows that p is odd. Let n = pα q.
α−1 α−1
If α > 1, then p = Ψn = Ψpq (ap , bp ), but
p−1  
pα−1 pα−1 pα−1 pα−1 ϕ(pq) p p
X p
Ψpq (a ,b ) > (a −b ) >a −b = bk > p,
k=0
k

4
because p > 2, contradiction. Hence n = pq. Now we have

Ψq (ap , bp ) (ap − bp )ϕ(q) ap − b p (2p − 1)b 2p − 1

p = Ψn = > > > > .
Ψq (a + b)ϕ(q) a+b 2b + 1 3
This is impossible when p > 3, so p = 3. Since q < p the only cases to consider are n = 3
and n = 6.
If n = 3 the theorem is obviously true because a3 −b3 = (a−b)(a2 +ab+b2 ) and a−b = 1.
The case n = 6 remains, and indeed Zsigmondy fails here. From 3 = Ψ6 = a2 − ab + b2
we easily deduce that a = 2 and b = a − 1 = 1. 

3 Applications
In this section we present some elementary applications of Zsigmondy’s theorem. We
start with a similar theorem for sums of nth powers.

Zsigmondy’s theorem for sums. Let a, b ∈ N such that gcd(a, b) = 1 and n ∈ N,

n > 1. There exists a prime divisor of an + bn that does not divide ak + bk for all
k ∈ {1, 2, . . . , n − 1}, except for the case 23 + 13 .
Proof.
This is an immediate consequence of Zsigmondy’s theorem. For any positive integer n > 1
for which 2n does not give an exception on Zsigmondy’s theorem, a2n −b2n has a primitive
prime divisor p, dividing an − bn or an + bn .
Because p is primitive, p does not divide an − bn . Thus p | an + bn and p - a2k − b2k for
all k < n. This implies that p - ak + bk for all k < n. 

Note that the exception 26 − 16 is reflected in 23 + 13 . The case n = 2 and a + b a power

of 2 disappears because we only consider n > 1 here.

We give a few examples where Zsigmondy’s theorem can be used.

Example 1. Find all positive integers a, n > 1 and k for which 3k − 1 = an .

Solution.
Because −1 is not a quadratic residue modulo 3, we have that n is odd. From a+1 | an +1
we have that 3 | a + 1. If a 6= 2 or n 6= 3, an + 1 has a prime divisor different from 3,
which means an + 1 cannot be a power of 3.
The only remaining case is a = 2 and n = 3, giving the only solution (a, n, k) = (2, 3, 2).

Example 2. (IMO Shortlist 2002) Let p1 , p2 , . . . , pn be distinct primes greater than 3.

Show that 2p1 p2 ···pn + 1 has at least 4n divisors.

Solution.
Let a = p1 p2 · · · pn and b = 2a + 1. It is sufficient to prove that b has at least 2n prime
divisors. This is indeed true, because Zsigmondy’s theorem for sums says that as 3 - a,
2d + 1 introduces a new prime for every divisor d | a. As a has 2n divisors, b has at least
2n prime divisors, which is much bigger than the required 2n.

In fact, we have the following general result:

5
Theorem 8. Let a, b, n be positive integers such that 3 - n and gcd(a, b) = 1. Then
τ (an + bn ) > 2τ (n) . If n is odd and a − b > 1, then τ (an − bn ) > 2τ (n) .

Here τ counts the number of positive divisors. The proof is analoguous to the solution
of example 2. The conditions for the inequalites can be weakened by studying in which
cases ad ± bd does not contain a primitive prime divisor, for some d | n.

References
[1] G.D. Birkhoff, H.S. Vandiver, On the Integral Divisors of an − bn , 1904,
http://www.jstor.org/stable/info/2007263

[2] Y. Ge, Elementary Properties of Cyclotomic Polynomials,

http://www.yimin-ge.com/doc/cyclotomic_polynomials.pdf

[3] L. Thompson, Zsigmondy’s Theorem, 2009,

www.artofproblemsolving.com/Forum/download/file.php?id=25872

[4] A.H. Parvardi, Lifting The Exponent Lemma, 2011,

http://www.artofproblemsolving.com/Resources/Papers/LTE.pdf