Lemma › Guides › Zsigmondy's theorem: statement, exceptions and examples
Guide

Zsigmondy's theorem: statement, exceptions and examples

Zsigmondy's theorem is a statement that a number is not made only of old primes. It is short to state, it is heavy to prove, and in an olympiad it usually finishes a problem in one move. This guide gives the statement with both exceptions, shows how to use it, and says what to do when a grader may not accept a bare citation.

The statement

Let a>b≥1a > b \ge 1 be coprime integers and let n≥2n \ge 2. A prime pp is primitive for an−bna^n - b^n if it divides an−bna^n - b^n but divides none of ak−bka^k - b^k for k<nk < n. Zsigmondy's theorem says a primitive prime always exists, with exactly two exceptions:

For the plus sign there is one exception. If n≥2n \ge 2, the number an+bna^n + b^n has a prime factor that divides no ak−bka^k - b^k with k<2nk < 2n, except for (a,b,n)=(2,1,3)(a, b, n) = (2, 1, 3). The bound 2n2n is there because an+bna^n + b^n divides a2n−b2na^{2n} - b^{2n}: this is the earlier statement applied to a2n−b2na^{2n} - b^{2n}.

Take b=1b = 1 to get the version you will meet most often. For a≥2a \ge 2 and n≥2n \ge 2, the number an−1a^n - 1 has a prime factor that divides none of a−1,a2−1,…,an−1−1a - 1, a^2 - 1, \dots, a^{n-1} - 1, unless n=2n = 2 and a+1a + 1 is a power of 22, or (a,n)=(2,6)(a, n) = (2, 6).

What the exceptions look like

Know the two exceptions as concrete numbers, because a problem written to test you will sit right on them.

The case (2,1,6)(2, 1, 6): 26−1=63=32⋅72^6 - 1 = 63 = 3^2 \cdot 7. The prime 33 already divides 22−1=32^2 - 1 = 3, and the prime 77 already divides 23−1=72^3 - 1 = 7. Every prime in 6363 was used up earlier.

The case n=2n = 2: a2−b2=(a−b)(a+b)a^2 - b^2 = (a - b)(a + b). The two factors share at most a factor of 22, because aa and bb are coprime. If a+ba + b is a power of 22, its only prime is 22, and 22 already divides a−ba - b. For a=7a = 7 and b=1b = 1 you get 72−1=48=24⋅37^2 - 1 = 48 = 2^4 \cdot 3, and both 22 and 33 already divide 7−1=67 - 1 = 6.

The case (2,1,3)(2, 1, 3) for the plus sign: 23+1=9=322^3 + 1 = 9 = 3^2, and 33 divides 2+12 + 1, which sits inside 22−12^2 - 1.

Where the primitive prime comes from

A primitive prime for an−bna^n - b^n is a prime pp for which a/ba/b has order exactly nn modulo pp. Here the order of a/ba/b is the smallest k≥1k \ge 1 with ak≡bk(modp)a^k \equiv b^k \pmod p, and the guide to orders has the details. That fact has an easy half: such a prime satisfies p≡1(modn)p \equiv 1 \pmod n. The hard half is that one always exists outside the exceptions, and the standard proof uses cyclotomic polynomials. You will not write that in an exam.

The two halves give you the working rule. A primitive prime is large, at least n+1n + 1, and it is tied to nn by the congruence. That makes it easy to bound things with and hard to hide.

A worked problem

Find all integers a≥2a \ge 2 and n≥2n \ge 2 such that an−1a^n - 1 is a power of 22.

Suppose an−1=2ka^n - 1 = 2^k. Any prime dividing an−1a^n - 1 is 22. Suppose a primitive prime existed. It would be 22, which means 22 does not divide a−1a - 1. Then aa is even, and an−1a^n - 1 is odd, so an−1=1a^n - 1 = 1. That has no solution with a≥2a \ge 2 and n≥2n \ge 2.

So no primitive prime exists, and we are in an exception. The case (2,6)(2, 6) gives 6363, which is not a power of 22. The remaining case is n=2n = 2 with a+1=2ma + 1 = 2^m, so a=2m−1a = 2^m - 1. Then

a2−1=(2m−2)⋅2m=2m+1(2m−1−1).a^2 - 1 = (2^m - 2) \cdot 2^m = 2^{m+1}\left(2^{m-1} - 1\right).

This is a power of 22 exactly when 2m−1−1=12^{m-1} - 1 = 1, that is m=2m = 2 and a=3a = 3. The only solution is 32−1=83^2 - 1 = 8.

Every step of that is ordinary except the sentence "a primitive prime exists unless". The theorem did the work that would otherwise need a tangle of case checks.

When to reach for it

What a grader accepts

Zsigmondy's theorem is well known. It is also a lot to hand a marker without a proof. Some contests accept a clear citation. Some do not. The safe course is to write the full statement, with both exceptions, in the line where you use it, and to check each exception explicitly afterwards, as the worked problem does. If the problem allows a cheaper argument, for example through the factorisation behind 2n−12^n - 1 prime forcing nn prime, use that and keep Zsigmondy for the case that has no other way in.

Mistakes to avoid

Forgetting the coprime condition is the common one. For a=4a = 4 and b=2b = 2 the theorem does not apply, because they share a factor. Divide it out first and work with 22 and 11. The other slip is applying it at n=1n = 1. There is no earlier term to compare with, and when a−b=1a - b = 1 the number a1−b1a^1 - b^1 has no prime factor at all. The theorem starts at n=2n = 2.

If you are drilling this, pick five numbers of the shape an−1a^n - 1 and factor them. For each, name the prime that is new and the exponent where it first appears. The pattern sticks after that. The problem archive holds the number theory problems linked above if you want to see the factorisations at work.

Related guides

Techniques in this guide

Train it on Lemma

Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.

Find your level