Zsigmondy's theorem

☆ Save On Wikipedia ↗

In number theory, Zsigmondy's theorem, named after Karl Zsigmondy, states that if a > b > 0 {\displaystyle a>b>0} {\displaystyle a>b>0} are coprime integers, then for any integer n ≥ 1 {\displaystyle n\geq 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}} {\displaystyle a^{n}-b^{n}} and does not divide a k − b k {\displaystyle a^{k}-b^{k}} {\displaystyle a^{k}-b^{k}} for any positive integer k < n {\displaystyle k<n} {\displaystyle k<n}, with the following exceptions:

  • n = 1 {\displaystyle n=1} {\displaystyle n=1}, a − b = 1 {\displaystyle a-b=1} {\displaystyle a-b=1}; then a n − b n = 1 {\displaystyle a^{n}-b^{n}=1} {\displaystyle a^{n}-b^{n}=1} which has no prime divisors
  • n = 2 {\displaystyle n=2} {\displaystyle n=2}, a + b {\displaystyle 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})} {\displaystyle a^{2}-b^{2}=(a+b)(a^{1}-b^{1})} must be contained in a 1 − b 1 {\displaystyle a^{1}-b^{1}} {\displaystyle a^{1}-b^{1}}, which is also even
  • n = 6 {\displaystyle n=6} {\displaystyle n=6}, a = 2 {\displaystyle a=2} {\displaystyle a=2}, b = 1 {\displaystyle 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})} {\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} {\displaystyle n>1} and n {\displaystyle n} {\displaystyle n} is not equal to 6, then 2 n − 1 {\displaystyle 2^{n}-1} {\displaystyle 2^{n}-1} has a prime divisor not dividing any 2 k − 1 {\displaystyle 2^{k}-1} {\displaystyle 2^{k}-1} with k < n {\displaystyle k<n} {\displaystyle k<n}.

Similarly, a n + b n {\displaystyle 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} {\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] It is also used in mathematical olympiads.

History

The theorem was discovered by Karl Zsigmondy who proved it in 1892.

Generalizations

Let ( a n ) n ≥ 1 {\displaystyle (a_{n})_{n\geq 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}}\}.} {\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} {\displaystyle n} such that every prime dividing a n {\displaystyle a_{n}} {\displaystyle a_{n}} also divides some a m {\displaystyle a_{m}} {\displaystyle a_{m}} for some m < n {\displaystyle 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\}} {\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\}} {\displaystyle \{1,2,6,12\}}, and that of the Pell sequence is { 1 } {\displaystyle \{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}} {\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\}} {\displaystyle {\mathcal {Z}}(a_{n})\subseteq \{1\leq n\leq 30\}} (see (sequence A285314 in the OEIS), there are only 13 such n {\displaystyle 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}} {\displaystyle (W_{n})_{n\geq 1}} is an elliptic divisibility sequence, then its Zsigmondy set Z ( W n ) {\displaystyle {\mathcal {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})} {\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})} {\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.