Zsigmondy's Theorem

== Theorem ==
Let $a > b > 0$ be coprime positive integers.
Let $n \ge 1$ be a (strictly) positive integer.
Then there is a prime number $p$ such that
:$p$ divides $a^n - b^n$
:$p$ does not divide $a^k - b^k$ for all $k < n$
with the following exceptions:
:$n = 1$ and $a - b = 1$
:$n = 2$ and $a + b$ is a power of $2$
:$n = 6$, $a = 2$, $b = 1$
== Proof ==
We call a prime number primitive if it divides $a^n - b^n$ but not $a^k - b^k$ for any $k < n$.
Let $\map {\Phi_n} {x, y}$ denote the $n$th homogeneous cyclotomic polynomial.
By Product of Cyclotomic Polynomials:
:$a^n - b^n = \ds \prod_{d \mathop \divides n} \map {\Phi_d} {a, b}$
Thus any primitive prime divisor is a divisor of $\map {\Phi_n} {a, b}$.
We start by investigating to which extent the converse is true.
=== Upper bound on nonprimitive prime divisors ===
Let $p$ be a prime divisor of $\map {\Phi_n} {a, b}$ which is not primitive.
Then there exists $k \mid n$ with $k < n$ such that $p \divides a^k - b^k$.
From Product of Cyclotomic Polynomials:
:$p \divides \dfrac {a^n - b^n} {a^k - b^k}$
By P-adic Valuation of Difference of Powers with Coprime Exponent:
:$p \divides \dfrac n k$
In particular:
:$p \divides n$
Let $n = p^\alpha q$ with $p \nmid q$.
By Cyclotomic Polynomial of Index times Prime Power:
:$p \divides \map {\Phi_n} {a, b} \divides \map {\Phi_q} {a^{p^\alpha}, b^{p^\alpha} }$
By Fermat's Little Theorem:
:$p \divides \map {\Phi_q} {a, b}$
By Prime Divisors of Cyclotomic Polynomials:
:$p \equiv 1 \pmod q$
Thus $p$ is the largest prime divisor of $n$.
Next, we determine the valuation of $p$ in $\map {\Phi_n} {a, b}$.
By Multiplicative Order of Roots of Cyclotomic Polynomial Modulo Prime, if $d \divides n$ with $p \divides a^d - b^d$, then $q \divides d$.
By the Möbius Inversion Formula for Cyclotomic Polynomials:
:$\map {\Phi_n} {a, b} = \ds \prod_{d \mathop \divides n} \paren {a^d - b^d}^{\map \mu {n/d} }$
Taking the valuation:
:$\map {\nu_p} {\map {\Phi_n} {a, b} } = \ds \sum_{q \mathop \divides d \mathop \divides n} \map \mu {n / d} \cdot \map {\nu_p} {a^d - b^d}$
The only nonzero terms are for $d = n$ and $d = n / p$.
Thus:
:$\map {\nu_p} {\map {\Phi_n} {a, b} } = \map {\nu_p} {\dfrac {a^n - b^n} {a^{n / p} - b^{n / p} } }$
By Fermat's Little Theorem:
:$p \divides a^{n/p} - b^{n/p}$
If $p > 2$, then by the Lifting The Exponent Lemma:
:$\map {\nu_p} {\map {\Phi_n} {a, b} } = 1$
If $p = 2$, then $n$ is a power of $2$.
By Cyclotomic Polynomial of Index Power of Two:
:$\map {\Phi_n} {a, b} = a^{n/2} + b^{n/2}$
If $n > 2$, then by Square Modulo 4:
:$\map {\Phi_n} {a, b} \equiv 2 \pmod 4$
Thus:
:$\map {\nu_p} {\map {\Phi_n} {a, b} } = 1$
If $n = 2$ and $a + b$ is not a power of $2$, then any odd prime divisor of $a + b$ is primitive, and the theorem is true.
We may thus suppose $\map {\nu_p} {\map {\Phi_n} {a, b} } = 1$.
=== Lower bound on primitive prime divisors ===
If $\map {\Phi_n} {a, b}$ has no nonprimitive prime divisors, it suffices to show that $\size {\map {\Phi_n} {a, b} } > 1$.
By Trivial Estimate for Cyclotomic Polynomials:
:$\size {\map {\Phi_n} {a, b} } \ge \paren {a - b}^{\map \phi n} \ge 1$
with equality $n = 1$ and $a - b = 1$.
If $\map {\Phi_n} {a, b}$ has a nonprimitive prime divisor $p \divides n$, let $n = p^\alpha q$ with $p \nmid q$.
We have to show that $\map {\Phi_n} {a, b} > p$.
If $\alpha > 1$, then:
and the proof is complete.
Let $\alpha = 1$.
Then $n = p q$.
If $a - b > 1$ then:
with equality only if $n = 1$, in which case the theorem is trivially true.
If $a - b = 1$ then:
We have:
so:
:$\map {\Phi_n} {a, b} \ge \dfrac {2^p - 1} 3$
If $p \ge 5$, then:
:$\dfrac {2^p - 1} 3 > p$
and the proof is complete.
Let $p = 2$.
Then $n = 2^\alpha = 2$.
Because $a - b = 1$, any prime divisor of $a + b$ is then primitive.
Let $p = 3$.
Then $n = 3 q$.
From $p \equiv 1 \pmod q$ we have $n = 3$ or $n = 6$.
If $n = 3$, then:
:$a^n - b^n = a^2 + a b + b^2$
and any prime divisor of $a^2 + a b + b^2$ is primitive.
If $n = 6$, then:
:$\map {\Phi_n} {a, b} = a^2 - a b + b^2 = b^2 + b + 1$
Thus $\map {\Phi_6} {a, b} > 3$ unless $a = 2$ and $b = 1$.
== Also see ==
* Zsigmondy's Theorem for Sums
== Sources ==
* 
Category:Number Theory
Category:Cyclotomic Polynomials
Category:63