HOME

TheInfoList



OR:

In
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Math ...
, Zsigmondy's theorem, named after Karl Zsigmondy, states that if a>b>0 are
coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equival ...
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s, then for any
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
n \ge 1, there is a
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...
''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, 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 A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer  as the exponent. In a context where only integers are considered, is restricted to non-negati ...
; 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, 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. 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.


History

The theorem was discovered by Zsigmondy working in
Vienna en, Viennese , iso_code = AT-9 , registration_plate = W , postal_code_type = Postal code , postal_code = , timezone = CET , utc_offset = +1 , timezone_DST ...
from 1894 until 1925.


Generalizations

Let (a_n)_ be a sequence of nonzero integers. The Zsigmondy set associated to the sequence is the set \mathcal(a_n) = \. 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(a^n-b^n)\subset\, and Carmichael's theorem says that the Zsigmondy set of the
Fibonacci sequence In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
is \, and that of the Pell sequence is \. In 2001 Bilu, Hanrot, and Voutier proved that in general, if (a_n)_ is a
Lucas sequence In mathematics, the Lucas sequences U_n(P,Q) and V_n(P, Q) are certain constant-recursive integer sequences that satisfy the recurrence relation : x_n = P \cdot x_ - Q \cdot x_ where P and Q are fixed integers. Any sequence satisfying this r ...
or a
Lehmer sequence In mathematics, a Lehmer sequence is a generalization of a Lucas sequence. Algebraic relations If ''a'' and ''b'' are complex numbers with :a + b = \sqrt :ab = Q under the following conditions: * ''Q'' and ''R'' are relatively prime nonzero i ...
, then \mathcal(a_n) \subseteq \ (see , there are only 13 such ns, namely 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 13, 18, 30). Lucas and Lehmer sequences are examples of
divisibility sequence In mathematics, a divisibility sequence is an integer sequence (a_n) indexed by positive integers ''n'' such that :\textm\mid n\texta_m\mid a_n for all ''m'', ''n''. That is, whenever one index is a multiple of another one, then the co ...
s. It is also known that if (W_n)_ is an elliptic divisibility sequence, then its Zsigmondy set \mathcal(W_n) is finite. However, the result is ineffective in the sense that the proof does not give an explicit upper bound for the largest element in \mathcal(W_n), although it is possible to give an effective upper bound for the number of elements in \mathcal(W_n).P. Ingram, J.H. Silverman, Uniform estimates for primitive divisors in elliptic divisibility sequences, ''Number theory, Analysis and Geometry'', Springer-Verlag, 2010, 233-263.


See also

* Carmichael's theorem


References

* * * * *


External links

*{{Mathworld, urlname=ZsigmondyTheorem, title=Zsigmondy Theorem Theorems in number theory