Zsigmondy's theorem

On prime divisors of differences two nth powers

In number theory, Zsigmondy's theorem, named after Karl Zsigmondy, states that if a > b > 0 {\displaystyle a>b>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 < n {\displaystyle k<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 > 1 {\displaystyle n>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 < n {\displaystyle k<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]

History

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

Generalizations

Let ( 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 < n {\displaystyle m<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

References

  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.
  • K. Zsigmondy (1892). "Zur Theorie der Potenzreste". Journal Monatshefte für 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. 102 (1). American Mathematical Society: 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