Zsigmondy's Theorem

From ProofWiki
Jump to navigation Jump to search


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$


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 = \displaystyle \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} = \displaystyle \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} } = \displaystyle \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$.


$\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\mid a^{n/p}-b^{n/p}$.

If $p>2$, then by the Lifting The Exponent Lemma, $\nu_p(\Phi_n(a,b))=1$.

If $p=2$, then $n$ is a power of $2$.

By Cyclotomic Polynomial of Index Power of Two, $\Phi_n(a,b) = a^{n/2} + b^{n/2}$.

If $n>2$, then by Square Modulo 4, $\Phi_n(a,b)\equiv2\pmod4$.

Thus $\nu_p(\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 $\nu_p(\Phi_n(a,b))=1$.

Lower bound on primitive prime divisors

If $\Phi_n(a,b)$ has no nonprimitive prime divisors, it suffices to show that $|\Phi_n(a,b)|>1$.

By Trivial Estimate for Cyclotomic Polynomials, $|\Phi_n(a,b)| \ge (a-b)^{\phi(n)} \ge 1$ with equality if and only if $n=1$ and $a-b=1$.

If $\Phi_n(a,b)$ has a nonprimitive prime divisor $p\mid n$, let $n=p^\alpha q$ with $p\nmid q$.

We have to show that $\Phi_n(a,b) > p$.

If $\alpha>1$, then:

\(\displaystyle \map {\Phi_n} {a, b}\) \(=\) \(\displaystyle \Phi_{p^{\alpha-1}q}(a^p, b^p)\) Cyclotomic Polynomial of Index times Prime Power
\(\displaystyle \) \(\ge\) \(\displaystyle a^p- b^p\) Trivial Estimate for Cyclotomic Polynomials
\(\displaystyle \) \(\ge\) \(\displaystyle (b+1)^p - b^p\)
\(\displaystyle \) \(>\) \(\displaystyle b p\) Binomial Theorem
\(\displaystyle \) \(\ge\) \(\displaystyle p\)

and we're done.

Let $\alpha = 1$.

Then $n = p q$.

If $a - b > 1$ then:

\(\displaystyle \map {\Phi_n} {a, b}\) \(\ge\) \(\displaystyle (a-b)^{\phi(n)}\) Trivial Estimate for Cyclotomic Polynomials
\(\displaystyle \) \(\ge\) \(\displaystyle 2^{p - 1}\) $a - b \ge 2$
\(\displaystyle \) \(\ge\) \(\displaystyle p\)

with equality only if $n=1$, in which case the theorem is trivially true.

If $a-b=1$ then:

\(\displaystyle \map {\Phi_n} {a, b}\) \(=\) \(\displaystyle \frac{\Phi_q(a^p, b^p)}{\Phi_q(a,b)}\) Cyclotomic Polynomial of Index times Prime Power
\(\displaystyle \) \(\ge\) \(\displaystyle \frac{(a^p- b^p)^{\phi(q)} }{(a+b)^{\phi(q)} }\) Trivial Estimate for Cyclotomic Polynomials

We have:

\(\displaystyle \frac{a^p-b^p}{a+b}\) \(=\) \(\displaystyle \frac{(b+1)^p-b^p}{2b+1}\) $a-b=1$
\(\displaystyle \) \(\ge\) \(\displaystyle \frac{(2^p-1)b}{2b+1}\) Binomial Theorem
\(\displaystyle \) \(\ge\) \(\displaystyle \frac{2^p-1}3\)
\(\displaystyle \) \(\ge\) \(\displaystyle 1\)

so $\map {\Phi_n} {a, b} \ge \dfrac {2^p - 1} 3$.

If $p \ge 5$, then $\dfrac {2^p - 1} 3 > p$ and we're done.

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


Source of Name

This entry was named for Karl Zsigmondy.

Also see