In number theory, Zsigmondy's theorem, named after Karl Zsigmondy, states that if are coprimeintegers, then for any integer , there is a prime numberp (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]
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 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 OEIS: A285314, 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]
^A. S. Bang (1886). "Taltheoretiske Undersøgelser". Tidsskrift for Mathematik. 5. Mathematica Scandinavica. 4: 70–80. JSTOR 24539988. And Bang, A. S. (1886). "Taltheoretiske Undersøgelser (continued, see p. 80)". Tidsskrift for Mathematik. 4: 130–137. JSTOR 24540006.
^Montgomery, H. "Divisibility of Mersenne Numbers." 17 Sep 2001.
zsigmondy, theorem, number, theory, named, after, karl, zsigmondy, states, that, displaystyle, coprime, integers, then, integer, displaystyle, there, prime, number, called, primitive, prime, divisor, that, divides, displaystyle, does, divide, displaystyle, pos. In number theory Zsigmondy s theorem named after Karl Zsigmondy states that if a gt b gt 0 displaystyle a gt b gt 0 are coprime integers then for any integer n 1 displaystyle n geq 1 there is a prime number p called a primitive prime divisor that divides a n b n displaystyle a n b n and does not divide a k b k displaystyle a k b k for any positive integer k lt n displaystyle k lt n with the following exceptions n 1 displaystyle n 1 a b 1 displaystyle a b 1 then a n b n 1 displaystyle a n b n 1 which has no prime divisors n 2 displaystyle n 2 a b displaystyle a b a power of two then any odd prime factors of a 2 b 2 a b a 1 b 1 displaystyle a 2 b 2 a b a 1 b 1 must be contained in a 1 b 1 displaystyle a 1 b 1 which is also even n 6 displaystyle n 6 a 2 displaystyle a 2 b 1 displaystyle b 1 then a 6 b 6 63 3 2 7 a 2 b 2 2 a 3 b 3 displaystyle a 6 b 6 63 3 2 times 7 a 2 b 2 2 a 3 b 3 This generalizes Bang s theorem 1 which states that if n gt 1 displaystyle n gt 1 and n displaystyle n is not equal to 6 then 2 n 1 displaystyle 2 n 1 has a prime divisor not dividing any 2 k 1 displaystyle 2 k 1 with k lt n displaystyle k lt n Similarly a n b n displaystyle a n b n has at least one primitive prime divisor with the exception 2 3 1 3 9 displaystyle 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 2 3 Contents 1 History 2 Generalizations 3 See also 4 References 5 External linksHistory EditThe theorem was discovered by Zsigmondy working in Vienna from 1894 until 1925 Generalizations EditLet a n n 1 displaystyle a n n geq 1 be a sequence of nonzero integers The Zsigmondy set associated to the sequence is the set Z a n n 1 a n has no primitive prime divisors displaystyle mathcal Z a n n geq 1 a n text has no primitive prime divisors i e the set of indices n displaystyle n such that every prime dividing a n displaystyle a n also divides some a m displaystyle a m for some m lt n displaystyle m lt n Thus Zsigmondy s theorem implies that Z a n b n 1 2 6 displaystyle 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 displaystyle 1 2 6 12 and that of the Pell sequence is 1 displaystyle 1 In 2001 Bilu Hanrot and Voutier 4 proved that in general if a n n 1 displaystyle a n n geq 1 is a Lucas sequence or a Lehmer sequence then Z a n 1 n 30 displaystyle mathcal Z a n subseteq 1 leq n leq 30 see OEIS A285314 there are only 13 such n displaystyle n 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 W n n 1 displaystyle W n n geq 1 is an elliptic divisibility sequence then its Zsigmondy set Z W n displaystyle mathcal Z W n 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 Z W n displaystyle mathcal Z W n although it is possible to give an effective upper bound for the number of elements in Z W n displaystyle mathcal Z W n 6 See also EditCarmichael s theoremReferences Edit A S Bang 1886 Taltheoretiske Undersogelser Tidsskrift for Mathematik 5 Mathematica Scandinavica 4 70 80 JSTOR 24539988 And Bang A S 1886 Taltheoretiske Undersogelser continued see p 80 Tidsskrift for Mathematik 4 130 137 JSTOR 24540006 Montgomery H Divisibility of Mersenne Numbers 17 Sep 2001 Artin Emil August 1955 The Orders of the Linear Groups Comm Pure Appl Math 8 3 355 365 doi 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 K Zsigmondy 1892 Zur Theorie der Potenzreste Journal Monatshefte fur Mathematik 3 1 265 284 doi 10 1007 BF01692444 hdl 10338 dmlcz 120560 Th Schmid 1927 Karl Zsigmondy Jahresbericht der Deutschen Mathematiker Vereinigung 36 167 168 Moshe Roitman 1997 On Zsigmondy Primes Proceedings of the American Mathematical Society 125 7 1913 1919 doi 10 1090 S0002 9939 97 03981 6 JSTOR 2162291 Walter Feit 1988 On Large Zsigmondy Primes Proceedings of the American Mathematical Society American Mathematical Society 102 1 29 36 doi 10 2307 2046025 JSTOR 2046025 Everest Graham van der Poorten Alf Shparlinski Igor Ward Thomas 2003 Recurrence sequences Mathematical Surveys and Monographs Vol 104 Providence RI American Mathematical Society pp 103 104 ISBN 0 8218 3387 1 Zbl 1033 11006 External links EditWeisstein Eric W Zsigmondy Theorem MathWorld Retrieved from https en wikipedia org w index php title Zsigmondy 27s theorem amp oldid 1169013750, wikipedia, wiki, book, books, library,