In number theory, Zsigmondy's theorem, named after Karl Zsigmondy, states that if
are coprime integers, then for any integer
, there is a prime number p (called a primitive prime divisor) that divides
and does not divide
for any positive integer
, with the following exceptions: This generalizes Bang's theorem,[1] which states that if
is not equal to 6, then
has a prime divisor not dividing any
Similarly,
has at least one primitive prime divisor with the exception
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.
[2][3] The theorem was discovered by Zsigmondy working in Vienna from 1894 until 1925.
be a sequence of nonzero integers.
The Zsigmondy set associated to the sequence is the set i.e., the set of indices
such that every prime dividing
also divides some
Thus Zsigmondy's theorem implies that
, and Carmichael's theorem says that the Zsigmondy set of the Fibonacci sequence is
, and that of the Pell sequence is
In 2001 Bilu, Hanrot, and Voutier[4] proved that in general, if
is a Lucas sequence or a Lehmer sequence, then
(see OEIS: A285314, there are only 13 such
s, namely 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 13, 18, 30).
Lucas and Lehmer sequences are examples of divisibility sequences.
is an elliptic divisibility sequence, then its Zsigmondy set
is finite.
[5] However, the result is ineffective in the sense that the proof does not give an explicit upper bound for the largest element in
, although it is possible to give an effective upper bound for the number of elements in