Zsigmondy's Theorem and Applications

Zsigmondy's Theorem.

If $a>b>0$ are relatively prime integers, then, for all natural natural numbers $n$, there exists a prime number $p$ such that $p \mid \left( a^n - b^n \right)$ and $p \not\mid \left( a^k - b^k \right)$ for any positive integer $k < n$.

There are however a few exceptions.

• $a - b = 1$ and $n = 1$
• $a = 2$, $b = 1$, and $n = 6$
• $a + b$ is a power of $2$, and $n=2$.

A Sledgehammer: Zsigmondy's Theorem

There are some things that have become extraordinarily popular in olympiad number theory. One of them is Zsigmondy's theorem. Today we will discuss how to use it in solving problems, but for now we will not focus on the proof. Because Expii is not ready for the proof yet. When it is, we can hope to see the proof as well. But if the reader is interested, first study Cyclotomic Polynomials.

For a sequence of integers $a_1,\ldots,a_n,\ldots$ a prime number $p$ is a primitive divisor of $a_n$ if $p$ divides $a_n$ but $p$ doesn't divide $a_k$ for any $k<n$. R. D. Carmichael called such a prime intrinsic divisor. Consider the sequence $a_k=2^k-1$. $a_1=1,a_2=3,a_3=7,a_4=15$. Note that, $a_3$ has primitive divisor $7$ and $a_4$ has the primitive divisor $5$. Also, $a|b$ implies that $a$ divides $b$. We know that $a-b|a^n-b^n$, which we will use later.

Theorem (Zsigmondy's Theorem, $1882$) Let $a,b$ be co-prime integers and $n\geq1$ be an integer. $a^n-b^n$ has a primitive divisor except when: $a-b=1$, $n=1$ or $a=2,b=1$ and $n=6$ or $a+b$ is a power of $2$ and $n=2$. $a^n+b^n$ has a primitive divisor for $n\geq2$ except for the case $2^3+1^3$.

Now, we see some demonstrations of this theorem.

Problem Find all positive integers $(a,n,x,y,z)$ so that \begin{align*} a^n-1 & = (a^x-1)(a^y-1)(a^z-1) \end{align*} If $a,n\geq3$ and $n>x,y,z$, we already know from the theorem that $a^n-1$ has a prime divisor that none of $a^x-1,a^y-1$ or $a^z-1$ has. Therefore, two sides can never be equal. We are left with cases $n\leq3$. Note that, $n\notin\{x,y,z\}$. But $a^x-1$ divides $a^n-1$, so $x$ divides $n$. Thus, $n>x,y,z$ and hence $a,n\leq3$, like we said before.

Now, either $a<3$ or $n<3$. If $a<3$, then $a=2$ so \begin{align*} 2^n-1 & = (2^x-1)(2^y-1)(2^z-1) \end{align*} Here, only exception is $n=6$ and $2^6-1=63=3\cdot3\cdot7=(2^2-1)(2^2-1)(2^3-1)$. So, $\{x,y,z\}=\{2,2,3\}$. Only $n<3$ is left to deal with.If $n=2$, then we don't have any solutions.

Problem If $p$ and $q$ are distinct odd primes, show that $2^{pq}-1$ has at least three distinct prime divisors.

Without loss of generality, consider that $2<q<p<pq$. Then $2^q-1$ has at least one prime factor, $2^p-1$ has a prime factor that is not in $2^q-1$ and $2^{pq}-1$ has a prime factor that is not in any of $2^p-1$ or $2^q-1$. Since $2^p-1|2^{pq}-1$ and $2^{q}-1|2^{pq}-1$, we have three distinct prime factors.

Problem Find all prime $p$ and positive integers $n$ so that \begin{align*} a^3+b^3=p^n \end{align*}

To apply the theorem, first we need to make $a$ and $b$ co-prime. If $q$ is a prime divisor of $(a,b)=g$, then $q|p$. Therefore, $g=p^r$ for some $r$. Let, $a=p^rx,b=p^ry$ with $x\bot y$. Then, \begin{align*} x^3+y^3 & = p^{n-3r} \end{align*} Assume that $m=n-3r$. Since $m=3$, we need to consider the exceptional case first. $x=2,y=1$ when $p=3$ and $n-3r=2$ produces infinite solutions. Otherwise, $x^3+y^3$ has a prime divisor that does not divide $x+y$. Obviously $x+y$ is divisible by $p$ since $x+y>1$. This is a contradiction. We have the infinite family of solutions: \begin{align*} \boxed{(a,b,n)=(2p^r,p^r,3r+2),(p^r,2p^r,3r+2)} \end{align*}

I hope I could send the message regarding the use of this theorem. But to be honest, I do not like to use such strong theorems for overkill when there are more elementary approaches available.