Zsigmondy's theorem

(Redirected from Zsigmondy theorem)

In number theory, Zsigmondy's theorem, named after Karl Zsigmondy, states that if are coprime integers, then for any integer , there is a prime number p (called a primitive prime divisor) that divides and does not divide for any positive integer , with the following exceptions:

  • , ; then which has no prime divisors
  • , a power of two; then any odd prime factors of must be contained in , which is also even
  • , , ; then

This generalizes Bang's theorem,[1] which states that if and is not equal to 6, then has a prime divisor not dividing any with .

Similarly, has at least one primitive prime divisor with the exception .

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

edit

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

Generalizations

edit

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[4] proved that in general, if   is a Lucas sequence or a Lehmer sequence, then   (see OEISA285314, there are only 13 such  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   is an elliptic divisibility sequence, then its Zsigmondy set   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  , although it is possible to give an effective upper bound for the number of elements in  .[6]

See also

edit

References

edit
  1. ^ A. S. Bang (1886). "Taltheoretiske Undersøgelser". Tidsskrift for Mathematik. 5. 4. Mathematica Scandinavica: 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.
edit