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 integer n ≥ 1, there is a prime number p (called a primitive prime divisor) that divides aⁿ − bⁿ and does not divide a^k − b^k for any positive integer k < n, with the following exceptions:

• n = 1, a − b = 1; then aⁿ − bⁿ = 1 which has no prime divisors
• n = 2, a + b a power of two; then any odd prime factors of a² - b² = (a + b)(a¹ - b¹) must be contained in a¹ - b¹, which is also even
• n = 6, a = 2, b = 1; then a⁶ − b⁶ = 63 = 3²×7 = (a² − b²)²(a³ − b³)

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

Similarly, aⁿ + bⁿ has at least one primitive prime divisor with the exception 2³ + 1³ = 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]

History

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

Generalizations

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]

See also

• Carmichael's theorem

References

1. A. S. Bang (1886). "Taltheoretiske Undersøgelser". Tidsskrift for Mathematik. 5. Mathematica Scandinavica. 4: 70–80. JSTOR 24539988. And Bang, A. S. (1886). "Taltheoretiske Undersøgelser (continued, see p. 80)". Tidsskrift for Mathematik. 4: 130–137. JSTOR 24540006.
2. Montgomery, H. "Divisibility of Mersenne Numbers." 17 Sep 2001.
3. Artin, Emil (August 1955). "The Orders of the Linear Groups". Comm. Pure Appl. Math. 8 (3): 355–365. doi:10.1002/cpa.3160080302.
4. Y. Bilu, G. Hanrot, P.M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers, J. Reine Angew. Math. 539 (2001), 75-122
5. J.H. Silverman, Wieferich's criterion and the abc-conjecture, J. Number Theory 30 (1988), 226-237
6. P. Ingram, J.H. Silverman, Uniform estimates for primitive divisors in elliptic divisibility sequences, Number theory, Analysis and Geometry, Springer-Verlag, 2010, 233-263.

• 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. American Mathematical Society. 102 (1): 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. 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.