In number theory, Zsigmondy's theorem, named after Karl Zsigmondy, states that if a > b > 0 {\displaystyle a>b>0} are coprime integers, then for any integer n ≥ 1 {\displaystyle n\geq 1} , there is a prime number p (called a primitive prime divisor) that divides a n − b n {\displaystyle a^{n}-b^{n}} and does not divide a k − b k {\displaystyle a^{k}-b^{k}} for any positive integer k < n {\displaystyle k<n} , with the following exceptions:
n = 1 {\displaystyle n=1} , a − b = 1 {\displaystyle a-b=1} ; then a n − b n = 1 {\displaystyle a^{n}-b^{n}=1} which has no prime divisors
n = 2 {\displaystyle n=2} , a + b {\displaystyle a+b} a power of two; then any odd prime factors of a 2 − b 2 = ( a + b ) ( a 1 − b 1 ) {\displaystyle a^{2}-b^{2}=(a+b)(a^{1}-b^{1})} must be contained in a 1 − b 1 {\displaystyle a^{1}-b^{1}} , which is also even
n = 6 {\displaystyle n=6} , a = 2 {\displaystyle a=2} , b = 1 {\displaystyle b=1} ; then a 6 − b 6 = 63 = 3 2 × 7 = ( a 2 − b 2 ) 2 ( a 3 − b 3 ) {\displaystyle a^{6}-b^{6}=63=3^{2}\times 7=(a^{2}-b^{2})^{2}(a^{3}-b^{3})}
This generalizes Bang's theorem, which states that if n > 1 {\displaystyle n>1} and n {\displaystyle n} is not equal to 6, then 2 n − 1 {\displaystyle 2^{n}-1} has a prime divisor not dividing any 2 k − 1 {\displaystyle 2^{k}-1} with k < n {\displaystyle k<n} . Similarly, a n + b n {\displaystyle a^{n}+b^{n}} has at least one primitive prime divisor with the exception 2 3 + 1 3 = 9 {\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. It is also used in mathematical olympiads.
History The theorem was discovered by Karl Zsigmondy who proved it in 1892.
Generalizations Let ( a n ) n ≥ 1 {\displaystyle (a_{n})_{n\geq 1}} be a sequence of nonzero integers. The Zsigmondy set associated to the sequence is the set
Z ( a n ) = { n ≥ 1 : a n has no primitive prime divisors } . {\displaystyle {\mathcal {Z}}(a_{n})=\{n\geq 1:a_{n}{\text{ has no primitive prime divisors}}\}.}
i.e., the set of indices n {\displaystyle n} such that every prime dividing a n {\displaystyle a_{n}} also divides some a m {\displaystyle a_{m}} for some m < n {\displaystyle m<n} . Thus Zsigmondy's theorem implies that Z ( a n − b n ) ⊂ { 1 , 2 , 6 } {\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 { 1 , 2 , 6 , 12 } {\displaystyle \{1,2,6,12\}} , and that of the Pell sequence is { 1 } {\displaystyle \{1\}} . In 2001 Bilu, Hanrot, and Voutier proved that in general, if ( a n ) n ≥ 1 {\displaystyle (a_{n})_{n\geq 1}} is a Lucas sequence or a Lehmer sequence, then Z ( a n ) ⊆ { 1 ≤ n ≤ 30 } {\displaystyle {\mathcal {Z}}(a_{n})\subseteq \{1\leq n\leq 30\}} (see (sequence A285314 in the OEIS), there are only 13 such n {\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 ( W n ) n ≥ 1 {\displaystyle (W_{n})_{n\geq 1}} is an elliptic divisibility sequence, then its Zsigmondy set Z ( W n ) {\displaystyle {\mathcal {Z}}(W_{n})} is finite. However, the result is ineffective in the sense that the proof does not give an explicit upper bound for the largest element in Z ( W n ) {\displaystyle {\mathcal {Z}}(W_{n})} , although it is possible to give an effective upper bound for the number of elements in Z ( W n ) {\displaystyle {\mathcal {Z}}(W_{n})} .
See also Carmichael's theorem Wilson prime Kaprekar's constant Fermat's little theorem Palindromic numbers Harshad numbers Dirichlet's theorem on arithmetic progressions
References
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.
External links Weisstein, Eric W. "Zsigmondy Theorem". MathWorld.