Zsigmondy's theorem

From Wikipedia, the free encyclopedia
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]


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


Let be a sequence of nonzero integers. The Zsigmondy set associated to the sequence is the set

i.e., the set of indices such that every prime dividing also divides some for some . Thus Zsigmondy's theorem implies that , and Carmichael's theorem says that the Zsigmondy set of the Fibonacci sequence is , and that of the Pell sequence is . In 2001 Bilu, Hanrot, and Voutier[1] proved that in general, if is a Lucas sequence or a Lehmer sequence, then . Lucas and Lehmer sequences are examples of divisibility sequences.

It is also known that if is an elliptic divisibility sequence, then its Zsigmondy set 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 , although it is possible to give an effective upper bound for the number of elements in .[3]

See also[edit]


  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.

External links[edit]