Fact-checked by Grok 2 weeks ago

Zsigmondy's theorem

Zsigmondy's theorem is a fundamental result in number theory that establishes the existence of a primitive prime divisor—a prime that divides a^n - b^n but does not divide a^k - b^k for any positive integer k < n—for coprime positive integers a > b \geq 1 and integer n \geq 2, with only two exceptional cases: when n=2 and a + b is a power of 2, or when a=2, b=1, and n=6.^[1] The theorem was proved by the Austrian mathematician Karl Zsigmondy in his 1892 paper "Zur Theorie der Potenzreste," published in Monatshefte für Mathematik und Physik.^[1] A special case where b=1 had been established earlier by the Danish mathematician Sophus Bang in 1886, focusing on Mersenne numbers of the form $2^n - 1.^[2] Zsigmondy also provided a parallel result for sums a^n + b^n when n is odd, guaranteeing a primitive prime divisor except for the case a=2, b=1, n=3.^[1] These primitive prime divisors are crucial because they ensure that the terms in the sequence a^n - b^n introduce new prime factors as n increases, beyond the exceptions.^[3] Zsigmondy's theorem has wide-ranging applications in algebra and number theory, including proofs of the infinitude of certain primes, analysis of cyclotomic polynomials, and establishing distinct orders of finite groups such as symmetric and alternating groups. It is frequently employed in Olympiad problems to resolve Diophantine equations and divisor properties, as seen in contests like the IMO Shortlist and national mathematics olympiads.^[4] Generalizations extend the theorem to Lucas and Lehmer sequences, elliptic curves, and algebraic number fields, highlighting its enduring influence on modern research in arithmetic progressions and primitive divisors.^[5]

Theorem Statement

Precise Formulation

A primitive prime divisor of a^n - b^n is a prime number p such that p divides a^n - b^n but does not divide a^k - b^k for any positive integer k < n. For such a prime p, since \gcd(a, b) = 1, p does not divide a or b, and the multiplicative order of a b^{-1} modulo p is exactly n.^[6] Zsigmondy's theorem asserts that for positive integers a > b \geq 1 with \gcd(a, b) = 1 and integer n > 1, the number a^n - b^n possesses at least one primitive prime divisor, except in two specific cases.^[1]^[7]

Exceptional Cases

Zsigmondy's theorem guarantees the existence of a primitive prime divisor for a^n - b^n when a > b \geq 1, \gcd(a, b) = 1, and n > 1, except when n = 2 and a + b is a power of 2, or when (a, b, n) = (2, 1, 6).^[8]^[7]^[3] For (a, b, n) = (2, 1, 6), compute $2^6 - 1^6 = 64 - 1 = 63 = [3^2](/page/3-2) \cdot [7](/page/+7). The proper divisors of 6 are 1, 2, and 3. The prime 3 divides $2^2 - 1^2 = 3 (and the order of $2 \cdot 1^{-1} modulo 3 is 2), while 7 divides $2^3 - 1^3 = 7 (order of $2 \cdot 1^{-1} modulo 7 is 3). Thus, neither prime is primitive for n = 6, as both divide $2^d - 1^d for some d < 6 dividing 6. This verifies the absence of a primitive prime divisor.^[8]^[3]^[4] In the cases where n = 2 and a + b = 2^k for k \geq 2, a^2 - b^2 = (a - b)(a + b). Since \gcd(a, b) = 1 and a + b even, both a and b are odd, so a - b is even and thus divisible by 2. The factor a + b = 2^k has only the prime factor 2, which also divides a - b = a^1 - b^1. Therefore, all prime factors of a^2 - b^2 divide some a^d - b^d for d < 2, so there are no primitive prime divisors. For example, with a = 3, b = 1 (k = 2), $3^2 - 1^2 = 8 = 2^3, and 2 divides $3 - 1 = 2; with a = 7, b = 1 (k = 3), $7^2 - 1^2 = 48 = 2^4 \cdot 3, and 3 divides $7 - 1 = 6 = 2 \cdot 3; with a = 15, b = 1 (k = 4), $15^2 - 1^2 = 224 = 2^5 \cdot 7, and 7 divides $15 - 1 = 14 = 2 \cdot 7; or with a = 5, b = 3 (k = 3), $5^2 - 3^2 = 16 = 2^4, and 2 divides $5 - 3 = 2. These factorizations confirm the lack of primitive primes in each instance.^[8]^[7]^[3]

Historical Development

Origins and Discovery

Karl Zsigmondy, an Austrian mathematician of Hungarian descent born on March 27, 1867, in Vienna, is credited with the discovery of Zsigmondy's theorem.^[9] He formulated and stated the theorem as part of his research in algebraic number theory during the late 19th century.^[10] Zsigmondy published the theorem in his 1892 paper titled "Zur Theorie der Potenzreste," which appeared in the Monatshefte für Mathematik und Physik, volume 3, issue 1, pages 265–284. In this work, he addressed the structure of prime divisors in sequences derived from powers, providing a general result on the existence of primitive prime factors. The theorem emerged from Zsigmondy's investigations into the factorization of expressions like a^n - 1, motivated by the need to understand how new prime factors appear in such sequences as n increases.^[11] This built directly on prior studies of specific cases, including Fermat numbers of the form $2^{2^n} + 1 and Mersenne numbers $2^p - 1, where patterns of primitive divisors had been noted but lacked a unified explanation.^[7] Zsigmondy's contribution generalized these observations, influenced by the era's advances in cyclotomic theory from figures like Leopold Kronecker.^[12]

Initial Proof and Influences

In his 1892 paper, Karl Zsigmondy provided the first complete proof of what is now known as Zsigmondy's theorem, establishing the existence of primitive prime divisors for a^n - b^n under the specified conditions. The proof centers on an assumption that no such primitive prime exists for a given n > 1, leading to a contradiction via properties of multiplicative orders in modular arithmetic. Specifically, Zsigmondy considered the cyclotomic polynomial \Phi_n(a) and showed that, absent a primitive prime divisor, \Phi_n(a) must divide \pm 1 or be a power of a prime already dividing a^d - b^d for some proper divisor d of n. This assumption implies that the order of a modulo any prime dividing \Phi_n(a) would be less than n, contradicting the degree and growth of \Phi_n(a), which exceeds the bounds imposed by earlier terms in the sequence. Zsigmondy's argument drew heavily from foundational results in number theory. The structure of cyclotomic polynomials, essential to expressing a^n - b^n as a product \prod_{d|n} \Phi_d(a), originated in Carl Friedrich Gauss's 1801 Disquisitiones Arithmeticae, where Gauss introduced these polynomials and their irreducibility over the integers. Additionally, the proof invoked Peter Gustav Lejeune Dirichlet's 1837 theorem on the infinite number of primes in arithmetic progressions to ensure the existence of primes with prescribed orders modulo which a behaves primitively, a key step in handling cases where potential divisors might otherwise recur from smaller exponents. Influences from Édouard Lucas's 1878 work on periodic numerical functions and primality tests for Mersenne numbers also informed the approach, particularly in analyzing divisor patterns in recursive sequences akin to powers. The theorem built upon earlier partial results, but more directly generalized the 1886 finding by Sophus Bang, who proved the existence of primitive primes for $2^n - 1 (the case a=2, b=1) for all n > 1 except n=6.^[13] Zsigmondy's generalization extended this to arbitrary coprime a > b \geq 1, unifying and broadening the scope to all such pairs while identifying the exceptional cases. While Zsigmondy's proof was groundbreaking, it relied on elementary modular techniques combined with Dirichlet's advanced density result, which some contemporaries viewed as non-elementary for the theorem's scope. Certain cases assumed the availability of primes in specific residue classes without full elementary justification at the time, prompting later refinements; for instance, Garrett Birkhoff and Harry Schultz Vandiver provided a more purely elementary proof in 1904, avoiding explicit use of Dirichlet's theorem by bounding the size of \Phi_n(a) more tightly through inequalities.

Mathematical Background

Cyclotomic Polynomials

The nth cyclotomic polynomial \Phi_n(x) is defined as the monic polynomial whose roots are the primitive nth roots of unity, that is,

\Phi_n(x) = \prod_{\substack{1 \leq k \leq n \\ \gcd(k,n)=1}} \left( x - e^{2\pi i k / n} \right),

where the product is over the integers k coprime to n. This polynomial has integer coefficients and is irreducible over the rational numbers \mathbb{Q}. Irreducibility over \mathbb{Q} for prime n was established by Gauss in his foundational work; the general case follows from later developments.^[14] A fundamental property of cyclotomic polynomials is their role in the factorization of x^n - 1:

x^n - 1 = \prod_{d \mid n} \Phi_d(x).

This relation implies that for any integer a > 1,

a^n - 1 = \prod_{d \mid n} \Phi_d(a).

The factorization is unique and provides a complete decomposition of a^n - 1 into irreducible factors over \mathbb{Q}.^[15] The degree of \Phi_n(x) is given by Euler's totient function \varphi(n), which counts the number of integers up to n that are coprime to n. An explicit formula for \Phi_n(x) can be derived using Möbius inversion:

\Phi_n(x) = \prod_{d \mid n} (x^{n/d} - 1)^{\mu(d)},

where \mu is the Möbius function, defined as \mu(m) = 1 if m is a square-free positive integer with an even number of prime factors, \mu(m) = -1 if m has an odd number of prime factors, and \mu(m) = 0 if m has a squared prime factor.^[16] This formula facilitates computation and analysis of the coefficients, which are integers bounded in absolute value by n for sufficiently large n, though they can vary in sign.^[15] In the context of integer values, primes dividing \Phi_n(a) for integer a > 1 are candidates for primitive divisors of a^n - 1, as such primes divide a^n - 1 but not a^d - 1 for any proper divisor d of n. This property underscores the utility of cyclotomic polynomials in studying the prime factors of sequences like a^n - 1.^[16] Basic examples illustrate these polynomials explicitly. For n=1, \Phi_1(x) = x - [1](/page/1). For n=2, \Phi_2(x) = x + [1](/page/−1). For n=3, \Phi_3(x) = x^2 + x + [1](/page/1). For n=4, \Phi_4(x) = x^2 + [1](/page/1). For n=6, \Phi_6(x) = x^2 - x + [1](/page/1). These cases demonstrate the increasing complexity with n while adhering to the degree \varphi(n).^[15]

Primitive Divisors

In the context of sequences like a^n - [1](/page/1) for integers a > 1 and n \geq 1, a primitive divisor is defined as a prime p that divides a^n - [1](/page/1) but does not divide a^k - [1](/page/1) for any positive integer k < n.^[17] This condition ensures that p first appears in the factorization at the n-th term of the sequence.^[3] The notion of primitive divisors is intimately connected to the multiplicative order of a modulo p. Specifically, if p divides a^n - 1, then the multiplicative order of a modulo p—the smallest positive integer d such that a^d \equiv 1 \pmod{p}—divides n.^[18] For p to be a primitive divisor, this order must be exactly n, meaning p does not divide a^d - 1 for any proper divisor d of n.^[17] Equivalently, p divides the n-th cyclotomic polynomial evaluated at a, denoted \Phi_n(a), if and only if the order of a modulo p is precisely n.^[3] Such primes exhibit key properties tied to modular arithmetic: since the order n divides p-1, it follows that p \equiv 1 \pmod{n} (assuming p does not divide a), and p cannot be 2 in most cases.^[3] These properties distinguish primitive divisors from earlier ones in the sequence, as any prime dividing a^d - 1 for d < n would have order dividing d, hence properly dividing n.^[18] For the general case of Zsigmondy's theorem, primitive prime divisors of a^n - b^n (with a > b \geq 1 coprime integers) are primes p dividing a^n - b^n but not a^k - b^k for k < n. These arise from primes dividing the norm from \mathbb{Q}(\zeta_n) of \Phi_n(a/b), ensuring new prime factors except in the exceptional cases. This algebraic perspective extends the rational case and is central to the theorem's proof.^[1] The concept relates to algebraic number theory through the splitting of primes in the cyclotomic field \mathbb{Q}(\zeta_n), the n-th cyclotomic extension of the rationals. Primes p \equiv 1 \pmod{n} (not dividing n) split completely in this field, enabling the existence of primitive divisors, whereas inert primes (with residue degree \phi(n)) or ramified primes (dividing n) typically do not contribute new primitive divisors at level n.^[3] Primitive divisors play a crucial role in ensuring that "new" primes continually appear in the factorizations of a^n - b^n as n increases, preventing the prime factors from stabilizing and guaranteeing an infinite supply of distinct primes dividing terms in the sequence.^[17] This property underpins the infinitude of primes in certain arithmetic progressions and supports broader results in Diophantine equations and factorization problems.^[3]

Proof Outline

Preliminary Lemmas

The proof of Zsigmondy's theorem relies on several preliminary lemmas that establish key properties of divisors and valuations in the context of cyclotomic polynomials and primitive divisors. These lemmas provide the foundational tools for deriving contradictions in the absence of primitive prime divisors.^[3] One exceptional case requires direct verification: for a = 2, b = 1, and n = 6, the number $2^6 - 1 = 63 = 3^2 \cdot 7 has no primitive prime divisor, as 3 divides $2^2 - 1 = 3 and 7 divides $2^3 - 1 = 7. This is confirmed by explicit factorization, showing all prime factors divide $2^k - 1 for some proper divisor k of 6.^[3]^[19] A crucial tool is the lifting the exponent lemma (LTE), which bounds the p-adic valuation of differences of powers. For an odd prime p not dividing a or b, with p dividing a - b, the valuation satisfies v_p(a^n - b^n) = v_p(a - b) + v_p(n). This lemma applies to bound the multiplicity of primes dividing \Phi_n(a, b), where \Phi_n(a, b) = b^{\varphi(n)} \Phi_n(a/b), ensuring that such primes cannot have high powers without violating the structure of earlier terms.^[3]^[19] Another essential result concerns the prime divisors of the cyclotomic polynomial evaluation: for integers a \geq 2 and n > 1, every prime divisor p of \Phi_n(a) satisfies either p \equiv 1 \pmod{n} (implying p \geq n + 1 > n) or p \mid n; moreover, due to the size of \Phi_n(a) > 1 and limitations on powers of small primes, \Phi_n(a) cannot be a prime power composed solely of primes dividing n in non-exceptional cases. Thus, \Phi_n(a) introduces new prime factors beyond those ≤ n, except in verified exceptions.^[3] The order lemma provides insight into the multiplicative order: if a prime p divides a^n - b^n and p does not divide a or b, then the order \mathrm{ord}_p(a/b) divides n and \mathrm{ord}_p(a/b) > 1. Moreover, if p divides \Phi_n(a, b), then \mathrm{ord}_p(a/b) = n exactly. This ensures that primes dividing \Phi_n(a, b) cannot arise from earlier cyclotomic factors without contradicting the order condition.^[3]^[20] To set up the contradiction, assume there is no primitive prime divisor for a^n - b^n. Then \Phi_n(a, b) must divide some product of earlier a^d - b^d for proper divisors d \mid n, implying \Phi_n(a, b) = \pm p^k for some prime p dividing an earlier term (so \mathrm{ord}_p(a/b) \mid d < n). However, the order lemma requires \mathrm{ord}_p(a/b) = n, a contradiction unless the case falls into verified exceptions like n=6, a=2, b=1. Combined with LTE and bounds on prime divisors, this forces \Phi_n(a, b) to be too large or structurally impossible for non-exceptional cases.^[3]^[19]

Core Argument

The core argument of Zsigmondy's theorem proceeds by contradiction, assuming that a^n - b^n has no primitive prime divisor for coprime integers a > b \geq 1 and n \geq 2 outside the exceptional cases. The proof reduces to analyzing the cyclotomic factor \Phi_n(a, b) = b^{\varphi(n)} \Phi_n(a/b), where the ratio a/b plays the role analogous to a in the b=1 case. Since a^n - b^n = \prod_{d \mid n} \Phi_d(a, b), and the \Phi_d(a, b) for distinct d are pairwise coprime (as established in preliminary lemmas), if there is no primitive prime divisor, then all prime factors of \Phi_n(a, b) must divide some \prod_{e \mid m} \Phi_e(a, b) for proper divisors m < n. Thus, \Phi_n(a, b) must equal \pm 1 or \pm p^k for some prime p and integer k \geq 1, where p divides an earlier \Phi_d(a, b) for d < n. However, preliminary lemmas confirm that |\Phi_n(a, b)| > 1 for a > b \geq 1 coprime and n > 1, ruling out the case \Phi_n(a, b) = \pm 1. The key step leverages growth estimates on |\Phi_n(a, b)|, which satisfy \log |\Phi_n(a, b)| \approx \phi(n) \log (a/b), where \phi is Euler's totient function; for n sufficiently large, this exceeds any bound compatible with \pm p^k where p is a prime dividing an earlier term. Specifically, bounds from the lemmas show |\Phi_n(a, b)| > (a/b)^{\phi(n)/c} for some constant c > 1, ensuring it cannot be a power of a single prime from prior terms. To obtain the contradiction, suppose \Phi_n(a, b) = \pm p^k. Then p divides \Phi_d(a, b) for some proper divisor d \mid n, d < n. Order arguments from the lemmas imply that the multiplicative order of a/b modulo p divides d < n. Yet, since p \mid \Phi_n(a, b), this order must equal n, yielding an impossibility. In cases where p divides n, additional bounds from the lemmas show that |\Phi_n(a, b)| exceeds the possible value of p^k. The argument distinguishes between even and odd n. For odd n, the direct properties of the cyclotomic polynomial \Phi_n(a, b) suffice, as the factorization of a^n - b^n aligns without additional sign complications. For even n, the proof incorporates factors from a^{n/2} + b^{n/2} (arising in the algebraic identity a^n - b^n = (a^{n/2} - b^{n/2})(a^{n/2} + b^{n/2})), using lemmas to ensure primitive divisors appear in \Phi_n(a, b) or the relevant subfactors while avoiding overlaps with earlier terms. This establishes the existence of a primitive prime divisor except in the exceptional cases, which are verified explicitly through direct computation for small n.

Examples and Applications

Illustrative Examples

A primitive prime divisor of a^n - 1 is a prime p dividing a^n - 1 such that the multiplicative order of a modulo p is exactly n, meaning p does not divide a^k - 1 for any positive integer k < n.^[20] To identify such divisors in practice, one factors a^n - 1 into primes and, for each prime factor p, computes the smallest positive integer k such that a^k \equiv 1 \pmod{p}; if this order equals n, then p is primitive.^[3] For a = 2 and n = 3, $2^3 - 1 = 7, which is prime. The order of 2 modulo 7 is 3, since $2^1 = 2 \not\equiv 1 \pmod{7}, $2^2 = 4 \not\equiv 1 \pmod{7}, and $2^3 = 8 \equiv 1 \pmod{7}; thus, 7 is a primitive prime divisor.^[20] For a = 3 and n = 1, $3^1 - 1 = 2, which is prime. Although cases with n = 1 are typically excluded from the statement of Zsigmondy's theorem, 2 serves as a primitive prime divisor here, as there are no smaller positive k < 1 to check.^[7] For a = 10 and n = 4, $10^4 - 1 = 9999 = 3^2 \cdot 11 \cdot 101. The prime 3 divides $10^1 - 1 = 9, so its order is 1. The prime 11 divides $10^2 - 1 = 99, so its order divides 2. For 101, the order of 10 modulo 101 is 4, since $10^1 = 10 \not\equiv 1 \pmod{101}, $10^2 = 100 \equiv -1 \not\equiv 1 \pmod{101}, and $10^4 \equiv 1 \pmod{101}; thus, 101 is a primitive prime divisor. For a = 5 and n = 5, $5^5 - 1 = 3124 = 2^2 \cdot 11 \cdot 71. The prime 2 divides $5^1 - 1 = 4, so its order is 1. For 11, the order of 5 modulo 11 is 5, since $5^5 \equiv 1 \pmod{11} and no smaller positive exponent works (5 being prime). Similarly, the order of 5 modulo 71 is 5; thus, both 11 and 71 are primitive prime divisors, illustrating that the theorem guarantees at least one but allows more. For a general case with b > 1, consider a=3, b=2, n=3: $3^3 - 2^3 = 19, which is prime. It does not divide $3^1 - 2^1 = 1 or $3^2 - 2^2 = 5, so the order condition holds and 19 is a primitive prime divisor.

Applications in Number Theory

Zsigmondy's theorem plays a key role in primitive prime generation by ensuring that, for most exponents n ≥ 2, the numbers a^n - 1 and a^n + 1 possess primitive prime divisors that do not divide a^k ± 1 for any k < n, thereby guaranteeing the introduction of new primes in sequences like those compiled in the Cunningham tables. These tables systematically record factorizations of a^n ± 1 for bases a up to 12 and large n, facilitating the discovery of large primes essential for cryptographic applications, including the generation of RSA keys in factoring challenges such as the former RSA Factoring Challenge.^[21] The theorem also connects to Artin's conjecture on primitive roots by implying that, for a fixed integer a > 1 that is neither -1 nor a perfect square, there are infinitely many primes p such that the multiplicative order of a modulo p is a prime number, as primitive prime divisors of a^q - 1 for prime q yield such p where the order is exactly q. This provides a partial affirmative result toward the conjecture, which posits infinitely many p where the order is precisely p-1.^[22]^[23] In algebraic number theory, Zsigmondy's theorem aids in bounding class numbers of cyclotomic fields through the factorization of cyclotomic polynomials Φ_n(a), as the existence of primitive prime divisors ensures a sufficient number of distinct prime ideals splitting in the extension ℚ(ζ_n), helping to estimate the ideal class group size via Dedekind's discriminant formula and ramification analysis.^[24] Variants of the Lucas-Lehmer primality test for generalized Mersenne numbers, such as a^p - 1 for prime p, rely on primitive divisors guaranteed by Zsigmondy's theorem to verify the absence of small factors and confirm primality, extending the classical test for Mersenne primes (a=2) to broader families like Lehmer sequences.^[25] In modern computational number theory, software like PARI/GP implements functions for computing the primitive part of a^n - 1, given by the evaluation of the n-th cyclotomic polynomial at a, \Phi_n(a) = \prod_{d \mid n} (a^{n/d} - 1)^{\mu(d)}^[26], leveraging Zsigmondy's theorem to verify the presence of primitive divisors in factorizations, which is vital for algebraic factoring and primality proving in large integer computations.^[27]

Generalizations and Extensions

Extensions to a^n + 1

Zsigmondy's theorem extends naturally to the sequence a^n + 1 when n is an odd integer greater than or equal to 3 and a \geq 2 is an integer. In this case, a^n + 1 possesses a primitive prime divisor, defined as a prime p dividing a^n + 1 such that p does not divide a^d + 1 for any positive integer d < n. Such a prime p satisfies a^n \equiv -1 \pmod{p}, implying that the multiplicative order of a modulo p is exactly $2n. The exceptions to this statement are limited. For n = 1, a + 1 generally lacks a primitive prime divisor in the sequence sense, as it is the first term. Additionally, the specific case a = 2, n = 3 yields $2^3 + 1 = 9 = 3^2, which has no primitive prime divisor. No other exceptions occur for odd n \geq 3 and a \geq 2. This result follows as a corollary of the general Zsigmondy theorem applied to a^n - (-1)^n, since n odd implies (-1)^n = -1, so a^n + 1 = a^n - (-1)^n with \gcd(a, -1) = 1. The proof sketch mirrors the original theorem's approach but adapts to the factorization of x^n + 1. Specifically, x^n + 1 = \prod_{\substack{d \mid 2n \\ d \nmid n}} \Phi_d(x), where \Phi_d(x) is the d-th cyclotomic polynomial. Assuming no primitive prime divisor leads to a^n + 1 dividing a product of earlier terms a^d + 1 for proper divisors d of n, but the algebraic independence and growth estimates (e.g., via resultants or field extensions) yield a contradiction in degree or norm unless in the exceptional cases. Aurifeuillian factorizations may assist for specific a, but the cyclotomic decomposition handles the general argument. For example, consider a = 2, n = 5: $2^5 + 1 = 33 = 3 \times 11. Here, 3 divides $2^1 + 1 = 3, but 11 is primitive since it does not divide $2^1 + 1 = 3 or $2^3 + 1 = 9, and the order of 2 modulo 11 is 10, confirming it as a primitive prime divisor.

Broader Algebraic Generalizations

Zsigmondy's theorem has been generalized to the setting of algebraic number fields, where primitive divisors are replaced by primitive prime ideals. Specifically, for integers A and B in the ring of integers of a number field K, with |A| > |B| > 0 and \gcd(A, B) = 1, the ideal (A^n - B^n) in the ring of integers possesses a primitive prime ideal divisor for all sufficiently large n, meaning a prime ideal dividing A^n - B^n but not A^m - B^m for any m < n.^[28] This extends naturally to units \alpha in the ring of integers of cyclotomic fields \mathbb{Q}(\zeta_m), where the norm of \alpha^n - 1 from \mathbb{Q}(\zeta_m) to \mathbb{Q} has primitive prime ideal divisors except for finitely many n.^[28] A further generalization, developed by Filaseta, Ford, and Konyagin in connection with Schinzel's work on coverings of the integers, addresses irreducible polynomials f(x) \in \mathbb{Z} evaluated at integers a. For such f, the values f(a)^n - 1 possess primitive prime divisors for all sufficiently large n, provided f(a) \neq \pm 1. This result relies on irreducibility criteria tied to the existence of primitive factors, ensuring that the factorization of these expressions introduces new prime factors as n grows.^[29] Zsigmondy's theorem also connects to Schinzel's Hypothesis H, a broad conjecture on simultaneous prime values of irreducible polynomials over \mathbb{Z} with no fixed prime divisor. In particular, the primitive divisor property from Zsigmondy implies irreducibility for certain lacunary polynomials, such as those of the form x^n - 1 or related forms, by guaranteeing that their factors introduce distinct primes, preventing reducibility over \mathbb{Q} for large degrees.^[30] Extensions to more general exponential sequences include Lucas sequences, defined by U_n(P, Q) = \frac{\alpha^n - \beta^n}{\alpha - \beta}, where \alpha, \beta are roots of the characteristic equation X^2 - P X + Q = 0 with P, Q \in \mathbb{Z}, \alpha \neq \beta, and the discriminant D = P^2 - 4Q \neq 0. Under non-degeneracy conditions (i.e., \alpha + \beta \neq 0, \alpha \beta \neq 1), Stewart proved in 1977 that U_n(P, Q) has a primitive prime divisor for all n > n_0, where n_0 depends on P and Q. This was refined by Bilu, Hanrot, and Voutier in 2001, who showed that every non-degenerate Lucas sequence with |D| > 1 has a primitive divisor for all n > 30, providing a uniform bound and completing the classification of exceptions.^[31]^[32] Recent developments as of 2025 include analogues of Zsigmondy's theorem in function fields and under the abc-conjecture. For instance, results explore primitive divisors for polynomials and rational functions over number fields, with implications for irreducibility and prime factorization in algebraic settings. Additionally, studies on large Zsigmondy primes provide bounds on the size of primitive primes exceeding n + 1 or \log n, enhancing applications in Diophantine equations and group theory.^[33]^[34]

References

[1]
Zur Theorie der Potenzreste | Monatshefte für Mathematik
Cite this article. Zsigmondy, K. Zur Theorie der Potenzreste. Monatsh. f. Mathematik und Physik 3, 265–284 (1892). https://doi.org/10.1007/BF01692444.
[2]
[PDF] arXiv:2401.17727v2 [math.NT] 21 May 2025
May 21, 2025 · The special case where b = 1 was discovered earlier by Bang [1] in 1886. Lemma 2.1 (Zsigmondy's theorem). Let a, b ∈ N such that gcd(a, b) ...
[3]
[PDF] Zsigmondy's Theorem - Bart Michels
Dec 1, 2014 · This is indeed true, because Zsigmondy's theorem for sums says that as 3 - a, 2d + 1 introduces a new prime for every divisor d | a.
[4]
[PDF] Zsigmondy's Theorem - HKUST Math Department
Feb 4, 2012 · In this article we look at yet another mighty theorem, which was discovered by the Austro-Hungarian mathematician. Karl Zsigmondy in 1882 and ...
[5]
Zsigmondy's theorem and primitive divisors of the Lucas and ...
Nov 15, 2021 · This paper obtains analogues of Zsigmondy's theorem, which states that every term beyond the sixth in a sequence has a primitive prime divisor, ...Missing: original | Show results with:original
[6]
None
### Summary of Key Definitions and Theorem from arXiv:1504.02598
[7]
Zur Theorie der Potenzreste
Zur Theorie der Potenzreste. Von K. Zsigmondy in Wien. I. Die vorliegende Arbeit beseh~tigt sich haupts~chlioh mit der. LSsung des folgenden Problems: Es ...
[8]
Zsigmondy Theorem -- from Wolfram MathWorld
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 ...
[9]
Karl Zsigmondy - Scientific Library
Karl Zsigmondy was an Austrian mathematician of Hungarian ethnicity. He was a son of Adolf Zsigmondy from Pozsony, Kingdom of Hungary (now Bratislava, ...
[10]
Karl Zsigmondy - The Mathematics Genealogy Project
According to our current on-line database, Karl Zsigmondy has 1 student and 1 descendant. We welcome any additional information.Missing: MacTutor biography
[11]
Algebra & Number Theory vol. 7 (2013), no. 9 - MSP
[Zsigmondy 1892] K. Zsigmondy, “Zur Theorie der Potenzreste”, Monatsh. Math. Phys. 3:1 (1892),. 265–284. MR 1546236 Zbl 24.0176.02. Communicated by David ...
[12]
(PDF) Number-theoretic transforms and a theorem of SYLVESTER
The result is closely connected with a theorem of Sylvester, Kronecker and Zsigmondy concerning prime factorizations for values of cyclotomic polynomials.Missing: Karl | Show results with:Karl
[13]
[PDF] Cyclotomic polynomials - Jordan Bell
Apr 12, 2017 · Therefore Φn = q ∈ C[x], and because q ∈ Z[x] this means that Φn ∈ Z[x]. In fact, it can be proved that Φn is irreducible in Q[x]. Gauss states ...Missing: totient | Show results with:totient
[14]
Disquisitiones Arithmeticae : Carl Friedrich Gauss - Internet Archive
Dec 29, 2022 · Disquisitiones Arithmeticae. by: Carl Friedrich Gauss. Publication date: 1966. Collection: internetarchivebooks; inlibrary; printdisabled.
[15]
Disquisitiones arithmeticae : Gauss, Carl Friedrich, 1777-1855
Aug 11, 2018 · Disquisitiones arithmeticae. by: Gauss, Carl Friedrich, 1777-1855 ... PDF download · download 1 file · SEGMENT DATA download · download 1 file.
[16]
Download book PDF
... Washington. Introduction to. Cyclotomic Fields. Second Edition. , Springer. Page 5. Lawrence C. Washington. Mathematics Department. University of Maryland.
[17]
None
### Summary of Zsigmondy's Theorem Content
[18]
[PDF] arXiv:1202.3670v4 [math.HO] 25 Jul 2023
Jul 25, 2023 · vides Φm(a) if and only if the order of a(mod p) is m. (Here Φm(x) ... primitive prime divisor, 27; primitive Pythagorean triples, 17 ...
[19]
An Elementary Proof of Zsigmondy's Theorem - Yan Sheng's site
May 15, 2019 · Zsigmondy's theorem is a powerful result about the prime divisors of a n − b n a^n-b^n an−bn, and can be used to solve a variety of math ...
[20]
[PDF] Zsigmondy's Theorem - yamashita-lab.net
Aug 11, 2009 · We define nth cyclotomic polynomial as follows: Φn(x) = Y ζ ... We've proven Zsigmondy's Theorem! Lola Thompson (Dartmouth College). Zsigmondy's ...
[21]
[PDF] WHEN IS an + 1 THE SUM OF TWO SQUARES?
On Zsigmondy primes. Proc. Amer. Math. Soc., 125(7):1913–1919, 1997. [19] ... The Cunningham Project. http://homes.cerias.purdue.edu/~ssw/cun/index.html ...
[22]
[PDF] Multiplicative orders mod p - Paul Pollack
At least one of 2,3,5 is a primitive root for infinitely many primes p. That is, there is some a ∈ {2,3,5} such that o(a mod p) = p − 1 for.
[23]
[PDF] Artin's conjecture for primitive roots
Subject to the generalised Rie- mann hypothesis, Hooley proved that this modified density is the correct density of primes for which a is a primitive root. To ...Missing: Zsigmondy's | Show results with:Zsigmondy's
[24]
[PDF] Primitive prime divisors, rings of integers and class numbers in ...
Before studying the primitive prime divisors in arithmetic dynamics, people have proved the finiteness of Zsigmondy set for various sequences. A classical ...<|control11|><|separator|>
[25]
On divisors of Lucas and Lehmer numbers | Acta Mathematica
Dec 17, 2013 · A Lucas–Lehmer approach to generalised Lebesgue–Ramanujan–Nagell equations ... Acta Math., 211 (2013), 315–382. Google Scholar. Zsigmondy K.: Zur ...
[26]
Primitive divisors of the expression An - Bn in algebraic number fields.
Primitive divisors of the expression An - Bn in algebraic number fields. A. Schinzel Journal für die reine und angewandte Mathematik (1974)
[27]
ON AN IRREDUCIBILITY THEOREM OF A. SCHINZEL ...
Weconsider the non-reciprocal part of F(x) to be reducible. We begin the proof by constructing non-reciprocal polynomials u(x) and v(x) in Z[x].Missing: Zsigmondy | Show results with:Zsigmondy
[28]
Andrzej Schinzel, Selecta – Preface - EMS Press
... Schinzel generalized a classical theorem of Zsigmondy of 1892 (often called the Birkhoff–Vandiver theorem) on primitive divisors. The central theme of ...
[29]
[PDF] Primitive Divisors of Lucas and Lehmer Numbers
B" if p|[A″ – B"] and p/[4" - Bm] for 0 <m<n; here [x] denotes the principal ideal.
[30]
[PDF] Existence of Primitive Divisors of Lucas and Lehmer Numbers
May 24, 2006 · Abstract: We prove that for n > 30, every n-th Lucas and Lehmer number has a primitive divisor. This allows us to list all Lucas and Lehmer ...