Zsigmondy's theorem

In number theory, Zsigmondy's theorem, named after Karl Zsigmondy, states that if $a>b>0$ are coprime integers, then for any integer $n\geq 1$ , there is a prime number p (called a primitive prime divisor) that divides $a^{n}-b^{n}$ and does not divide $a^{k}-b^{k}$ for any positive integer $k<n$ , with the following exceptions:

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

Similarly, $a^{n}+b^{n}$ has at least one primitive prime divisor with the exception $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\geq 1}$ be a sequence of nonzero integers. The Zsigmondy set associated to the sequence is the set

{\mathcal {Z}}(a_{n})=\{n\geq 1:a_{n}{\text{ has no primitive prime divisors}}\}.

i.e., the set of indices $n$ such that every prime dividing $a_{n}$ also divides some $a_{m}$ for some $m<n$ . Thus Zsigmondy's theorem implies that ${\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\}$ , and that of the Pell sequence is $\{1\}$ . In 2001 Bilu, Hanrot, and Voutier[4] proved that in general, if $(a_{n})_{n\geq 1}$ is a Lucas sequence or a Lehmer sequence, then ${\mathcal {Z}}(a_{n})\subseteq \{1\leq n\leq 30\}$ (see OEIS: A285314, there are only 13 such $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\geq 1}$ is an elliptic divisibility sequence, then its Zsigmondy set ${\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 ${\mathcal {Z}}(W_{n})$ , although it is possible to give an effective upper bound for the number of elements in ${\mathcal {Z}}(W_{n})$ .[6]

References

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.
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 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. 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

Weisstein, Eric W. "Zsigmondy Theorem". MathWorld.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] 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.

[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.

Zsigmondy's theorem

History

Generalizations

See also

References

External links