View source for Rayl

In [[number theory]], '''Zsigmondy's theorem''', named after [[Karl Zsigmondy]], states that if ''a''&nbsp;>&nbsp;''b''&nbsp;>&nbsp;0 are [[coprime]] [[integer]]s, then for any [[natural number]] ''n''&nbsp;>&nbsp;1 there is a [[prime number]] ''p'' (called a ''primitive prime divisor'') that divides ''a<sup>n</sup>''&nbsp;&minus;&nbsp;''b<sup>n</sup>'' and does not divide ''a<sup>k</sup>''&nbsp;&minus;&nbsp;''b<sup>k</sup>'' for any positive integer ''k''&nbsp;<&nbsp;''n'', with the following exceptions:

*''a''&nbsp;=&nbsp;2, ''b''&nbsp;=&nbsp;1, and ''n''&nbsp;=&nbsp;6; or

*''a''&nbsp;+&nbsp;''b'' is a power of two, and ''n''&nbsp;=&nbsp;2.

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

Similarly, <math>a^n + b^n</math> has at least one primitive prime divisor with the exception <math>2^3 + 1^3 = 9</math>.

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 <math>(a_n)_{n\ge1}</math> be a sequence of nonzero integers.
The '''Zsigmondy set''' associated to the sequence is the set

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

i.e., the set of indices <math>n</math> such that every prime dividing <math>a_n</math>
also divides some <math>a_m</math> for some <math>m < n</math>. Thus Zsigmondy's theorem implies that <math>\mathcal{Z}(a^n-b^n)\subset\{1,2,6\}</math>, and [[Carmichael's theorem]] says that the
Zsigmondy set of the Fibonacci sequence is <math>\{1,2,6,12\}</math>. In 2001 Bilu, Hanrot, and 
Voutier<ref>Y. Bilu, G. Hanrot, P.M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers, ''J. Reine Angew. Math.'' '''539''' (2001), 75-122</ref>
proved that in general, if <math>(a_n)_{n\ge1}</math> is a [[Lucas sequence]] or a [[Lehmer number|Lehmer sequence]], then <math>\mathcal{Z}(a_n) \subseteq \{ 1 \le n \le 30 \}</math>.
Lucas and Lehmer sequences are examples of [[divisibility sequence]]s.

It is also known that
if <math>(W_n)_{n\ge1}</math> is an [[elliptic divisibility sequence]], then its Zsigmondy
set <math>\mathcal{Z}(W_n)</math> is finite.<ref>J.H. Silverman,
Wieferich's criterion and the ''abc''-conjecture,
''J. Number Theory'' '''30''' (1988), 226-237</ref> However, the result is ineffective in the sense
that the proof does give an explicit upper bound for the largest element in <math>\mathcal{Z}(W_n)</math>,
although it is possible to give an effective upper bound for the number of elements
in <math>\mathcal{Z}(W_n)</math>.<ref>P. Ingram, J.H. Silverman, Uniform estimates for primitive divisors in elliptic divisibility sequences, ''Number theory, Analysis and Geometry'', Springer-Verlag, 2010, 233-263.</ref>

==See also==
* [[Carmichael's theorem]]

== References ==
{{reflist}}
* {{cite journal
|title = Zur Theorie der Potenzreste
|author = K. Zsigmondy
|journal = Journal Monatshefte für Mathematik
|volume = 3
|issue = 1
|pages = 265–284
|year = 1892
|doi = 10.1007/BF01692444
}}
* {{cite journal
|title = Karl Zsigmondy
|author = Th. Schmid
|journal = Jahresbericht der Deutschen Mathematiker-Vereinigung
|volume = 36
|issue = 
|pages = 167–168
|year = 1927
|url = http://www.digizeitschriften.de/dms/img/?PPN=PPN37721857X_0036&DMDID=dmdlog18
|format = 
}} 
* {{cite journal
|title = On Zsigmondy Primes
|author = [[Moshe Roitman]]
|journal = Proceedings of the American Mathematical Society
|volume = 125
|issue = 7
|pages = 1913–1919
|year = 1997
|doi = 10.1090/S0002-9939-97-03981-6
|jstor=2162291
}}
* {{cite journal
|title = On Large Zsigmondy Primes
|author = [[Walter Feit]]
|journal = Proceedings of the American Mathematical Society
|volume = 102
|issue = 1
|pages = 29–36
|year = 1988
|doi = 10.2307/2046025
|jstor = 2046025
|publisher = [[American Mathematical Society]]
}}
* {{cite book | last1=Everest | first1=Graham | last2=van der Poorten | first2=Alf | author2-link=Alfred van der Poorten | last3=Shparlinski | first3=Igor | last4=Ward | first4=Thomas | title=Recurrence sequences | series=Mathematical Surveys and Monographs | volume=104 | location=[[Providence, RI]] | publisher=[[American Mathematical Society]] | year=2003 | isbn=0-8218-3387-1 | zbl=1033.11006 | pages=103–104 }}

== External links ==
*{{Mathworld|urlname=ZsigmondyTheorem|title=Zsigmondy Theorem}}

[[Category:Theorems in number theory]]