An Elementary Proof of Zsigmondy's Theorem
15 May 2019
Zsigmondy’s theorem is a powerful result about the prime divisors of $a^n-b^n$, and can be used to solve a variety of math olympiad problems (see for instance this blog post by KingSmasher3). In this post, I will present an elementary proof of Zsigmondy’s theorem.
The core idea of the proof can be summarised as follows:
Key Idea: Apply the LTE lemma to the context of cyclotomic polynomials.
All the technical results that we prove along the way will serve this single purpose.
The proof below is a cleaned-up version of this Stack Exchange answer.
Zsigmondy’s theorem
Zsigmondy’s Theorem (1892): Let $a>b\geq1$ be coprime integers, and let $n\geq2$. Then there exists a prime divisor of $a^n-b^n$ that does not divide $a^k-b^k$ for all $1\leq k< n$, except when:
- $n=2$, and $a+b$ is a power of $2$; or
- $(a,b,n)=(2,1,6)$.
We call such a prime a primitive prime divisor of $a^n-b^n$.
We shall first deal with the easy case $n=2$. If $a^2-b^2$ has no primitive prime divisors then any prime $p$ dividing $a+b$ must divide $a^2-b^2$, and thus must divide $a-b$. Then
$$
\begin{aligned}
p&\mid(a+b)+(a-b)=2a,\\
p&\mid(a+b)-(a-b)=2b,
\end{aligned}$$
so $p=2$ (since $a,b$ are coprime). Hence $a+b$ is a power of $2$. Henceforth we shall assume that $n\geq3$.
Lifting The Exponent lemma
For $p$ prime and $n\geq1$, let $v_p(n)$ denote the exponent of $p$ in the prime factorisation of $n$. The following is a well-known result within the math olympiad community, called the Lifting The Exponent (LTE) lemma.
LTE Lemma: Let $p$ be a prime, $x,y\in\bb Z$, and $m\geq1$, such that $x\equiv y\not\equiv0\pmod p$.
-
If $p\geq3$, then
$$v_p(x^m-y^m)=v_p(x-y)+v_p(m).$$
-
If $p=2$, then
$$
v_2(x^m-y^m)=\begin{cases}v_2(x^2-y^2)+v_2\left(\frac m2\right)&m\text{ even},\\v_2(x-y)&m\text{ odd}.\end{cases}\ \qed$$
The proof proceeds by expanding $\frac{x^m-y^m}{x-y}$, and studying the $v_p$ of each factor; you can refer to the detailed argument here.
We want to study $v_p(a^n-b^n)$ as a function of $n$. This is zero for all $n$ if $p$ divides either $a$ or $b$ ($p$ cannot divide both since they are coprime). Otherwise, let $k\geq1$ be minimal such that $p\mid a^k-b^k$. Then $k$ is the order of $\frac ab$ in the multiplicative group $(\bb Z/p\bb Z)^\times$, so
$$p\mid a^n-b^n\iff\left(\frac ab\right)^n\equiv1\pmod p\iff k\mid n.$$
In this case, by the LTE lemma we have
$$v_p(a^n-b^n)=v_p(a^k-b^k)+v_p\left(\frac nk\right).$$
Hence the first time that $p$ divides $a^n-b^n$ (ie. when $n=k$), we have no control over what power of $p$ divides it; but after that LTE determines the exponent completely.
Cyclotomic polynomials
For $n\geq1$, the primitive $n$-th roots of unity are the $\omega\in\bb C$ such that $\omega^n=1$, and $\omega^k\neq1$ for $1\leq k< n$. More explicitly, these are given by
$$\{\exp(\frac{2\pi ik}n)\,:\,1\leq k\leq n,\,\gcd(k,n)=1\}.$$
Hence there are precisely $\varphi(n)$ many primitive $n$-th roots of unity, where $\varphi$ denotes the Euler totient function.
The $n$-th cyclotomic polynomial $\Phi_n$ is defined by
$$\Phi_n(X)\coloneqq\prod_j(X-\omega_j),$$
where the product is taken over all primitive $n$-th roots of unity $\omega_j$. Note that the $n$-th roots of unity are precisely the union of the primitive $d$-th root of unity for $d\mid n$, so
$$X^n-1=\prod_{d\mid n}\Phi_d(X).$$
Theorem: For $n\geq1$, $\Phi_n(X)$ has integer coefficients.
Proof: We proceed by induction; for $n=1$ we have $\Phi_1(X)=X-1\in\bb Z[X]$.
Suppose that $\Phi_k(X)\in\bb Z[X]$ for all $k< n$. Then
$$X^n-1=\Phi_n(X)g_n(X),$$
where $g_n(X)$ is the product of all $\Phi_d(X)$ with $d\mid n$ and $d\neq n$. Then $g_n\in\bb Z[X]$ by induction hypothesis. By performing the long division $\Phi_n(X)=\frac{X^n-1}{g_n(X)}$, we have $\Phi_n\in\bb Q[X]$. Hence by Gauss’s lemma, we have $\Phi_n\in\bb Z[X]$, as desired. $\qed$
Proposition: Let $p$ be a prime and $n\geq1$. Then
$$
\Phi_{pn}(X)=\begin{cases}\Phi_n(X^p)&p\mid n\\\frac{\Phi_n(X^p)}{\Phi_n(X)}&p\nmid n.\end{cases}$$
Proof: If $p\mid n$, note that the $p$-th roots of the primitive $n$-th roots of unity are precisely the primitive $pn$-th roots of unity (eg. from the explicit formula for primitive roots of unity). Hence
$$\prod_j(X^p-\omega_j)=\prod_k(X-\rho_k),$$
where the product on LHS (resp. RHS) is over all primitive $n$-th (resp. $pn$-th) roots of unity. This gives the first statement.
If $p\nmid n$, note that the $p$-th roots of the primitive $n$-th roots of unity are precisely the union of the primitive $n$-th and $pn$-th roots of unity. A similar product to the above gives the second statement. $\qed$
Proposition: Let $n\geq3$ and $x\in(1,\infty)$. Then
$$
(x-1)^{\varphi(n)}<\Phi_n(x)< (x+1)^{\varphi(n)}.$$
Proof: For any primitive $n$-th root of unity $\omega$, we have $\lvert\omega\rvert=1$, so triangle inequality gives
$$x-1\leq\lvert x-\omega\rvert\leq x+1,$$
where the left (resp. right) equality holds if and only if $\omega=1$ (resp. $\omega=-1$). Since $n\geq3$, neither equality can hold for all $\omega$. Hence taking products over all $\omega$ gives
$$
(x-1)^{\varphi(n)}<\lvert\Phi_n(x)\rvert< (x+1)^{\varphi(n)}.$$
We finish by noting that $\Phi_n(x)>0$ for $x>1$ by induction on $n$, using $X^n-1=\prod_{d\mid n}\Phi_d(X)$. $\qed$
The expression $a^n-b^n$ is clearly related to the cyclotomic polynomials when $b=1$, since $a^n-1=\prod_{d\mid n}\Phi_n(a)$. For the case of general $b$, we can use the trick of homogenisation: define
$$\Phi_n(a,b)\coloneqq b^{\varphi(n)}\Phi_n\left(\frac ab\right).$$
Note that when expanding $\Phi_n\left(\frac ab\right)$, the denominators are powers of $b$ up to $b^{\varphi(n)}$; hence $\Phi_n(a,b)$ is an integer. Also,
$$
\begin{aligned}
\prod_{d\mid n}\Phi_n(a,b)&=\prod_{d\mid n}b^{\varphi(d)}\Phi_d\left(\frac ab\right)\\
&=b^n\left[\left(\frac ab\right)^n-1\right]\\
&=a^n-b^n.
\end{aligned}$$
Furthermore, we can easily check the following analogous results:
Proposition: Let $p$ be a prime and $n\geq1$. Then
$$
\Phi_{pn}(a,b)=\begin{cases}\Phi_n(a^p,b^p)&p\mid n\\\frac{\Phi_n(a^p,b^p)}{\Phi_n(a,b)}&p\nmid n.\end{cases}\ \qed$$
Proposition: Let $n\geq3$. Then
$$
(a-b)^{\varphi(n)}<\Phi_n(a,b)< (a+b)^{\varphi(n)}.\ \qed$$
LTE on cyclotomic polynomials
To execute the Key Idea, let’s see what LTE says about $v_p(\Phi_n(a,b))$.
Theorem: Let $p\geq3$ be a prime such that $p\nmid a,b$. Let $n\geq1$, and let $k\geq1$ be minimal such that $p\mid a^k-b^k$. Then
$$
v_p(\Phi_n(a,b))=\begin{cases}v_p(a^k-b^k)&n=k\\1&n=p^\beta k,\,\beta\geq1\\0&\text{else}.\end{cases}$$
Proof: Firstly, if $k\nmid n$ then $p\nmid a^n-b^n$ implies $p\nmid\Phi_n(a,b)$. Hence
$$
\begin{aligned}
v_p(a^k-b^k)&=v_p(\Phi_k(a,b))+\sum_{d\mid k,\,d\neq k}v_p(\Phi_d(a,b))\\
&=v_p(\Phi_k(a,b)),
\end{aligned}$$
which proves the first statement. Now LTE gives
$$
\begin{aligned}
v_p(a^k-b^k)+\beta&=v_p(a^{p^\beta k}-b^{p^\beta k})\\
&=\sum_{d\mid p^\beta k}v_p(\Phi_d(a,b))\\
&=\sum_{d\mid p^\beta k,\,d\mid k}v_p(\Phi_d(a,b))\\
&=v_p(a^k-b^k)+\sum_{j=1}^\beta v_p(\Phi_{p^jk}(a,b)).
\end{aligned}$$
Hence if $v_p(\Phi_{p^jk}(a,b))=1$ for all $1\leq j<\beta$ then $v_p(\Phi_{p^\beta k}(a,b))=1$ as well, and so the second statement follows by induction.
Finally, if $k\mid n$ then $n=p^\beta mk$ for some $p\nmid m$ (so $\beta=v_p(\frac nk)$). We have dealt with the case $m=1$. If $m>1$ then $\Phi_n(a,b)$ is a factor of
$$\frac{\prod_{d\mid n}\Phi_d(a,b)}{\prod_{d\mid p^\beta k}\Phi_d(a,b)}=\frac{a^n-b^n}{a^{p^\beta k}-b^{p^\beta k}}.$$
But LTE gives $v_p(a^n-b^n)=v_p(a^{p^\beta k}-b^{p^\beta k})$, so $p$ does not divide $\Phi_n(a,b)$, and we are done. $\qed$
For the case $p=2$, the slightly different form of LTE gives the following using exactly the same argument. (Note that in this case, we must have $k=1$ above.)
Theorem: Let $a,b$ be odd, and $n\geq1$. Then
$$
v_2(\Phi_n(a,b))=\begin{cases}v_2(a-b)&n=1\\v_2(a+b)&n=2\\1&n=2^\beta,\,\beta\geq2\\0&\text{else}.\end{cases}\ \qed$$
Proof of Zsigmondy’s theorem
We are now ready to prove Zsigmondy’s theorem for $a>b\geq1$ coprime integers and $n\geq3$. The plan is to use the previous results to severely restrict the possible values of $\Phi_n(a,b)$, which will almost always contradict the analytic bounds on $\Phi_n$.
Assume that $a^n-b^n$ has no primitive prime divisors. If $\Phi_n(a,b)$ has no prime factors then it is equal to $1$; otherwise let $p$ be any prime factor of $\Phi_n(a,b)$. Then $p\mid a^n-b^n$, so by assumption there exists a minimal $1\leq k< n$ such that $p\mid a^k-b^k$.
Now by the results of the previous section, $v_p(\Phi_n(a,b))\geq1$ implies $n=p^\beta k$ for some $\beta\geq1$, where $k$ is the order of $\frac ab$ in $(\bb Z/p\bb Z)^\times$. Hence $k\mid p-1$, so $k< p$. This implies that $p$ is in fact the largest prime factor of $n$ (if not, the largest prime factor of $n$ is larger than $p$ and divides $k$, contradiction).
If $p\geq3$, we immediately have $v_p(\Phi_n(a,b))=1$. Also, if $p=2$ then $n\geq3$ is a power of $2$, so $4\mid n$ implies
$$\Phi_n(a,b)=a^{n/2}+b^{n/2}\equiv2\pmod 4.$$
Thus $v_p(\Phi_n(a,b))=1$ also holds in this case. Therefore $\Phi_n(a,b)$ is either $1$ or $p$, the largest prime factor of $n$.
On the other hand, by our lower bound for $\Phi_n(a,b)$, we have
$$p\geq\Phi_n(a,b)\geq(a-b)^{\varphi(n)}\geq(a-b)^{p-1}.$$
If $a-b\geq2$, then equality can only hold if $p=2$ and $n=2$, contradicting $n\geq3$.
If $a-b=1$, write $n=p^\beta k$ as before. If $\beta\geq2$ then
$$
\begin{aligned}
p\geq\Phi_n(a,b)&=\Phi_{pk}(a^{p^{\beta-1}},b^{p^{\beta-1}})\\
&\geq(a^{p^{\beta-1}}-b^{p^{\beta-1}})^{\varphi(pk)}\\
&\geq a^p-b^p\\
&=pb^{p-1}+\cdots+1,\quad(\because a=b+1)
\end{aligned}$$
contradiction. Hence $\beta=1$, so $n=pk$. Thus we have
$$
\begin{aligned}
p\geq\Phi_n(a,b)&=\frac{\Phi_k(a^p,b^p)}{\Phi_k(a,b)}\\
&\geq\left(\frac{a^p-b^p}{a+b}\right)^{\varphi(k)}\\
&\geq\frac{\sum_{j=1}^b(j+1)^p-j^p}{a+b}\\
&\geq\frac{b(2^p-1)}{2b+1}\\
&\geq\frac{2^p-1}3.
\end{aligned}$$
Here, equality can only hold when $p=3$ and $b=1$ (so $a=2$). Also, since $k< p$, we have $k\in\{1,2\}$, so $n\in\{3,6\}$. It is now straightforward to check that $2^3-1^3$ has $7$ as a primitive divisor, but $2^6-1^6$ has no primitive divisors. This concludes the proof of Zsigmondy’s theorem.
