Zsigmondy's theorem explained
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
a6-b6=63=32 x 7=(a2-b2)2(a3-b3)
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
The theorem was discovered by Zsigmondy working in Vienna from 1894 until 1925.
Generalizations
Let
be a
sequence of nonzero integers.The
Zsigmondy set associated to the sequence is the
setl{Z}(an)=\{n\ge1:anhasnoprimitiveprimedivisors\}.
i.e., the set of indices
such that every prime dividing
also divides some
for some
. Thus Zsigmondy's theorem implies that
l{Z}(an-bn)\subset\{1,2,6\}
, 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
l{Z}(an)\subseteq\{1\len\le30\}
(see, 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 Zsigmondyset
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
References
- Zur Theorie der Potenzreste. K. Zsigmondy. Journal Monatshefte für Mathematik. 3. 1. 265–284. 1892. 10.1007/BF01692444. 10338.dmlcz/120560. free.
- Karl Zsigmondy. Th. Schmid. Jahresbericht der Deutschen Mathematiker-Vereinigung. 36. 167–168. 1927.
- On Zsigmondy Primes. Moshe Roitman. Proceedings of the American Mathematical Society. 125. 7. 1913–1919. 1997. 10.1090/S0002-9939-97-03981-6. 2162291. Moshe Roitman. free.
- On Large Zsigmondy Primes. Walter Feit. Proceedings of the American Mathematical Society. 102. 1. 29–36. 1988. 10.2307/2046025. 2046025. American Mathematical Society. Walter Feit. free.
- Book: Everest . Graham . van der Poorten . Alf . Alfred van der Poorten . Shparlinski . Igor . Ward . Thomas . Recurrence sequences . Mathematical Surveys and Monographs . 104 . . . 2003 . 0-8218-3387-1 . 1033.11006 . 103–104 .
Notes and References
- Taltheoretiske Undersøgelser. A. S. Bang. Tidsskrift for Mathematik. 5. 4. 70–80. 1886. 24539988. Mathematica Scandinavica. And Taltheoretiske Undersøgelser (continued, see p. 80). Tidsskrift for Mathematik. 4. 130–137. 24540006. Bang. A. S.. 1886.
- Montgomery, H. "Divisibility of Mersenne Numbers." 17 Sep 2001.
- Artin. Emil. Emil Artin. August 1955. The Orders of the Linear Groups. Comm. Pure Appl. Math.. 8. 3. 355-365. 10.1002/cpa.3160080302.
- Y. Bilu, G. Hanrot, P.M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers, J. Reine Angew. Math. 539 (2001), 75-122
- J.H. Silverman,Wieferich's criterion and the abc-conjecture,J. Number Theory 30 (1988), 226-237
- P. Ingram, J.H. Silverman, Uniform estimates for primitive divisors in elliptic divisibility sequences, Number theory, Analysis and Geometry, Springer-Verlag, 2010, 233-263.