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

  • $\begingroup$ 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$. $\endgroup$ – Will Fisher Jul 1 '17 at 21:29
  • 3
    $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Jul 1 '17 at 22:01
  • $\begingroup$ @ThomasAndrews How does that help solve the question? $\endgroup$ – user19405892 Jul 1 '17 at 23:43
  • $\begingroup$ 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$. $\endgroup$ – 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$.

  • 2
    $\begingroup$ Zsigmondy's theorem lists an exception for $n = 6, a = 2, b = 1$, but there $a^n-b^n$ is divisible by $7$. $\endgroup$ – ccorn Jul 2 '17 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.