Zsigmondy's theorem

From Wikipedia, the free encyclopedia

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

  • a = 2, b = 1, and n = 6; or
  • a + b is a power of two, and n = 2.

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, a^{n}+b^{n} has at least one primitive prime divisor with the exception 2^{3}+1^{3}=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

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

Generalizations

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

{\mathcal  {Z}}(a_{n})=\{n\geq 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\}. In 2001 Bilu, Hanrot, and Voutier[1] proved that in general, if (a_{n})_{{n\geq 1}} is a Lucas sequence or a Lehmer sequence, then {\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 (W_{n})_{{n\geq 1}} 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

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.

External links

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.