# Zsigmondy's theorem

In number theory, Zsigmondy's theorem, named after Karl Zsigmondy, states that if a > b > 0 are coprime integers, then for any natural number n > 1 there is a prime number p (called a primitive prime divisor) that divides anbn and does not divide akbk for any positive integer k < n, with the following exceptions:

• a = 2, b = 1, and n = 6; or
• a + b is a power of two, and n = 2.

This generalizes Bang's theorem, which states that if n > 1 and n is not equal to 6, then 2n − 1 has a prime divisor not dividing any 2k − 1 with k < n.

Similarly, an + bn has at least one primitive prime divisor with the exception 23 + 13 = 9.

Zsigmondy's theorem is often useful, especially in group theory, where it is used to prove that various groups have distinct orders except when they are known to be the same.

## History

The theorem was discovered by Zsigmondy working in Vienna from 1894 until 1925.

## Generalizations

Let $(a_n)_{n\ge1}$ be a sequence of nonzero integers. The Zsigmondy set associated to the sequence is the set

$\mathcal{Z}(a_n) = \{ n \ge 1 : a_n \text{ has no primitive prime divisors} \}.$

i.e., the set of indices $n$ such that every prime dividing $a_n$ also divides some $a_m$ for some $m < n$. Thus Zsigmondy's theorem implies that $\mathcal{Z}(a^n-b^n)\subset\{1,2,6\}$, and Carmichael's theorem says that the Zsigmondy set of the Fibonacci sequence is $\{1,2,6,12\}$. In 2001 Bilu, Hanrot, and Voutier[1] proved that in general, if $(a_n)_{n\ge1}$ is a Lucas sequence or a Lehmer sequence, then $\mathcal{Z}(a_n) \subseteq \{ 1 \le n \le 30 \}$. Lucas and Lehmer sequences are examples of divisibility sequences.

It is also known that if $(W_n)_{n\ge1}$ is an elliptic divisibility sequence, then its Zsigmondy set $\mathcal{Z}(W_n)$ is finite.[2] However, the result is ineffective in the sense that the proof does give an explicit upper bound for the largest element in $\mathcal{Z}(W_n)$, although it is possible to give an effective upper bound for the number of elements in $\mathcal{Z}(W_n)$.[3]