# Zsigmondy's theorem

Jump to: navigation, search

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 anbn and does not divide akbk for any positive integer k < n, with the following exceptions:

• n = 1, ab = 1; then anbn = 1 which has no prime divisors
• n = 2, a + b a power of two; then any odd prime factors of a² - b² = (a + b)(a1 - b1) must be contained in a1 - b1, which is also even
• n = 6, a = 2, b = 1; then a6b6 = 63 = 3²7 = (a2b2)2(a3b3)

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

Similarly, an + bn has at least one primitive prime divisor with the exception 23 + 13 = 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.[clarification needed]

## 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. 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[1] 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\}}$. 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.[2] However, the result is ineffective in the sense that the proof does 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})}$.[3]

## References

1. ^ Y. Bilu, G. Hanrot, P.M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers, J. Reine Angew. Math. 539 (2001), 75-122
2. ^ J.H. Silverman, Wieferich's criterion and the abc-conjecture, J. Number Theory 30 (1988), 226-237
3. ^ P. Ingram, J.H. Silverman, Uniform estimates for primitive divisors in elliptic divisibility sequences, Number theory, Analysis and Geometry, Springer-Verlag, 2010, 233-263.