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 be coprime integers and let . A prime is primitive for if it divides but divides none of for . Zsigmondy's theorem says a primitive prime always exists, with exactly two exceptions:
- and is a power of .
- .
For the plus sign there is one exception. If , the number has a prime factor that divides no with , except for . The bound is there because divides : this is the earlier statement applied to .
Take to get the version you will meet most often. For and , the number has a prime factor that divides none of , unless and is a power of , or .
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 : . The prime already divides , and the prime already divides . Every prime in was used up earlier.
The case : . The two factors share at most a factor of , because and are coprime. If is a power of , its only prime is , and already divides . For and you get , and both and already divide .
The case for the plus sign: , and divides , which sits inside .
Where the primitive prime comes from
A primitive prime for is a prime for which has order exactly modulo . Here the order of is the smallest with , and the guide to orders has the details. That fact has an easy half: such a prime satisfies . 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 , and it is tied to by the congruence. That makes it easy to bound things with and hard to hide.
A worked problem
Find all integers and such that is a power of .
Suppose . Any prime dividing is . Suppose a primitive prime existed. It would be , which means does not divide . Then is even, and is odd, so . That has no solution with and .
So no primitive prime exists, and we are in an exception. The case gives , which is not a power of . The remaining case is with , so . Then
This is a power of exactly when , that is and . The only solution is .
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
- Very few prime factors. An expression equals something like a power of a prime, a product of two given primes, or a factorial. A primitive prime has to be one of them, so you look for a contradiction with its size.
- A prime power on one side, an exponential on the other. Equations like or give a number whose prime factors you control.
- A statement about "a prime that divides this and nothing before". If the problem is worded around divisibility by for smaller , it is Zsigmondy in disguise.
- Gcd problems. The identity behind says the common prime factors come from a shared divisor of the exponents. For example . A primitive prime of divides no with , so it can never appear in a gcd like that.
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 prime forcing 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 and the theorem does not apply, because they share a factor. Divide it out first and work with and . The other slip is applying it at . There is no earlier term to compare with, and when the number has no prime factor at all. The theorem starts at .
If you are drilling this, pick five numbers of the shape 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
- Order modulo p in olympiad number theoryThe order of a modulo p divides p - 1 and every n with a^n = 1 mod p. How to use it to pin down prime factors, with a worked proof and the traps.
- Lifting the exponent lemma explained for competitionsThe lifting the exponent lemma in one line, the p = 2 version that catches almost everyone, and the signals that tell you a contest problem wants it.
- gcd(2^m − 1, 2^n − 1): the proof, and how to spot itWhy gcd(2^m − 1, 2^n − 1) = 2^gcd(m,n) − 1: run Euclid's algorithm on the exponents. A full proof, a second proof by orders, and where it turns up.
- Chinese remainder theorem in olympiad problemsThe Chinese remainder theorem for coprime moduli, how to solve a system by hand, what changes when moduli share a factor, and where olympiads use it.
- Legendre's formula for the power of a prime in n!Legendre's formula gives the exponent of a prime in n! as a sum of floors. The proof, the digit-sum form, trailing zeros, and the traps that cost marks.
Techniques in this guide
- Modular ThinkingWhen the numbers are too big, shrink the universe.
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