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 natural number n, 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:

  • a - b = 1, and n = 1;
  • a = 2, b = 1, and n = 6; or

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.

History[edit]

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

Generalizations[edit]

Let (a_n)_{n\ge1} be a sequence of nonzero integers. The Zsigmondy set associated to the sequence is the set


\mathcal{Z}(a_n) = \{ n \ge 1 : a_n \text{ has no primitive prime divisors} \}.

i.e., the set of indices n such that every prime dividing a_n also divides some a_m for some m < n. Thus Zsigmondy's theorem implies that \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\}, and that of the Pell sequence is \{1\}. In 2001 Bilu, Hanrot, and Voutier[1] proved that in general, if (a_n)_{n\ge1} is a Lucas sequence or a Lehmer sequence, then \mathcal{Z}(a_n) \subseteq \{ 1 \le n \le 30 \}. Lucas and Lehmer sequences are examples of divisibility sequences.

It is also known that if (W_n)_{n\ge1} is an elliptic divisibility sequence, then its Zsigmondy set \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 \mathcal{Z}(W_n), although it is possible to give an effective upper bound for the number of elements in \mathcal{Z}(W_n).[3]

See also[edit]

References[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]