Zsigmondy's theorem

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

• ${\displaystyle n=1}$, ${\displaystyle a-b=1}$; then ${\displaystyle a^{n}-b^{n}=1}$ which has no prime divisors
• ${\displaystyle n=2}$, ${\displaystyle a+b}$ a power of two; then any odd prime factors of ${\displaystyle a^{2}-b^{2}=(a+b)(a^{1}-b^{1})}$ must be contained in ${\displaystyle a^{1}-b^{1}}$, which is also even
• ${\displaystyle n=6}$, ${\displaystyle a=2}$, ${\displaystyle b=1}$; then ${\displaystyle a^{6}-b^{6}=63=3^{2}\times 7=(a^{2}-b^{2})^{2}(a^{3}-b^{3})}$

This generalizes Bang's theorem,^[1] which states that if ${\displaystyle n>1}$ and ${\displaystyle n}$ is not equal to 6, then ${\displaystyle 2^{n}-1}$ has a prime divisor not dividing any ${\displaystyle 2^{k}-1}$ with ${\displaystyle k<n}$.

Similarly, ${\displaystyle a^{n}+b^{n}}$ has at least one primitive prime divisor with the exception ${\displaystyle 2^{3}+1^{3}=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.^[2][3]

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

Let ${\displaystyle (a_{n})_{n\geq 1}}$ be a sequence of nonzero integers. The Zsigmondy set associated to the sequence is the set

${\displaystyle {\mathcal {Z}}(a_{n})=\{n\geq 1:a_{n}{\text{ has no primitive prime divisors}}\}.}$

i.e., the set of indices ${\displaystyle n}$ such that every prime dividing ${\displaystyle a_{n}}$ also divides some ${\displaystyle a_{m}}$ for some ${\displaystyle m<n}$. Thus Zsigmondy's theorem implies that ${\displaystyle {\mathcal {Z}}(a^{n}-b^{n})\subset \{1,2,6\}}$, and Carmichael's theorem says that the Zsigmondy set of the Fibonacci sequence is ${\displaystyle \{1,2,6,12\}}$, and that of the Pell sequence is ${\displaystyle \{1\}}$. In 2001 Bilu, Hanrot, and Voutier^[4] proved that in general, if ${\displaystyle (a_{n})_{n\geq 1}}$ is a Lucas sequence or a Lehmer sequence, then ${\displaystyle {\mathcal {Z}}(a_{n})\subseteq \{1\leq n\leq 30\}}$ (see OEIS: A285314, there are only 13 such ${\displaystyle n}$s, namely 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 13, 18, 30). Lucas and Lehmer sequences are examples of divisibility sequences.

It is also known that if ${\displaystyle (W_{n})_{n\geq 1}}$ is an elliptic divisibility sequence, then its Zsigmondy set ${\displaystyle {\mathcal {Z}}(W_{n})}$ 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 ${\displaystyle {\mathcal {Z}}(W_{n})}$, although it is possible to give an effective upper bound for the number of elements in ${\displaystyle {\mathcal {Z}}(W_{n})}$.^[6]

• Carmichael's theorem
• Wilson prime
• Kaprekar's constant
• Fermat's little theorem
• Babczynski theorem
• Palindromic numbers
• Harshad numbers
• Dirichlet's theorem on arithmetic progressions

• K. Zsigmondy (1892). "Zur Theorie der Potenzreste". Journal Monatshefte für Mathematik. 3 (1): 265–284. doi:10.1007/BF01692444. hdl:10338.dmlcz/120560.
• Th. Schmid (1927). "Karl Zsigmondy". Jahresbericht der Deutschen Mathematiker-Vereinigung. 36: 167–168.
• Moshe Roitman (1997). "On Zsigmondy Primes". Proceedings of the American Mathematical Society. 125 (7): 1913–1919. doi:10.1090/S0002-9939-97-03981-6. JSTOR 2162291.
• Walter Feit (1988). "On Large Zsigmondy Primes". Proceedings of the American Mathematical Society. 102 (1). American Mathematical Society: 29–36. doi:10.2307/2046025. JSTOR 2046025.
• Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas (2003). Recurrence sequences. Mathematical Surveys and Monographs. Vol. 104. Providence, RI: American Mathematical Society. pp. 103–104. ISBN 0-8218-3387-1. Zbl 1033.11006.

• Weisstein, Eric W. "Zsigmondy Theorem". MathWorld.