# Prove that there exists a prime $p$ such that $p \mid a^n-b^n$ and $p > n$

Let $1 < b < a$ be relatively prime positive integers and $n > 2$ a positive integer. Prove that there exists a prime $p$ such that $p \mid a^n-b^n$ and $p > n$.

I thought about using Zsigmondy's Theorem. Then we have $$p_1 \mid a-b,p_2 \mid a^2-b^2,a^3-b^3,p_3 \mid a^4-b^4,\ldots$$ where $p_i \nmid a^k-b^k$ for $k < i$. I didn't see how to use this to find a prime such that $p > n$.

• Zsigmondy's Theorem can be pretty easily used to show that there is a prime $p>2\sigma_0(n)-1$ such that $p\mid a^n-b^n$, but I can't seem to push this up to $n$. – Will Fisher Jul 1 '17 at 21:29
• If $p\leq n$ then $a^{p-1}-b^{p-1}$ is divisible by $p$, unless $p\mid ab$. If $p\mid a$ and $p\not\mid b$ then $p\not\mid a^n-b^n$ for any $n$. – Thomas Andrews Jul 1 '17 at 22:01
• @ThomasAndrews How does that help solve the question? – user19405892 Jul 1 '17 at 23:43
• Because if all $p\mid a^n-b^n$ were $\le n$ that would violate Zsigmondy's Theorem since every $p\mid a^n-b^n$ would divide $a^k-b^k$ where $k=p-1< n$. Of course with slight modification since $p$ may not divide $a^{p-1}-b^{p-1}$ if $p\mid a$ but $p\nmid b$, however the last sentence of Thomas' comment show this isn't ever the case if $p\mid a^n-b^n$. – Will Fisher Jul 2 '17 at 0:48

Since @ThomasAndrews has not written up an answer, I will put his answer (which is in the comments) here. Let $p$ be a prime, then we have three cases $$\begin{array}{c} p\mid a^{p-1}-b^{p-1} \\ \text{or} \\ p\mid a\;\text{ and }\; p\nmid b \\ \text{or} \\ p\nmid a \;\text{ and }\; p\mid b \end{array}$$ Where the top case follows from Fermat's Little Theorem when $p\nmid a$ and $p\nmid b$ and is trivial when $p\mid a$ and $p\mid b$; the last two cases are just the remaining options. Now suppose that $p\mid a^n-b^n$. We then know that $p$ satisfies the first case above, because if $p\mid a$ but $p\nmid b$ then we have $a^n-b^n\equiv 0\mod p\Rightarrow b^n\equiv a^n\equiv 0\mod p$ however that gives $p\mid b^n$ which is false when $p\nmid b$ (similar argument when $p\mid b$ but $p\nmid a$). Thus $$p\mid a^n-b^n\Rightarrow p\mid a^{p-1}-b^{p-1}$$ Now suppose all prime factors of $a^n-b^n$ were $\le n$, then the above tells us that $a^n-b^n$ has no prime factors not shared with $a^k-b^k$ for all $k<n$, since every prime factor, $p$, of $a^n-b^n$ divides $a^{p-1}-b^{p-1}$ where $p-1<n$. This however is a violation of Zsigmondy's Theorem, and thus there must exist a prime factor of $a^n-b^n$ that is $>n$.
• Zsigmondy's theorem lists an exception for $n = 6, a = 2, b = 1$, but there $a^n-b^n$ is divisible by $7$. – ccorn Jul 2 '17 at 18:17