Zsigmondy's theorem

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 sequenceis${\displaystyle \{1,2,6,12\}}$ , and that of the Pell sequenceis${\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})}$ isfinite.^[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

• 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.