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

Solution 1:

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