Let $p_{1},p_{2},p_{3}$ be different prime numbers, and let the positive integer $n$, be defined by $$n=p_{1}p_{2}p_{3}.$$

Show that:

For any two positive integer $a,b$ ,then $a^n-b^n$ always has a prime factor $P$ satisfying $P>n$

This problem is from a maths exam a few days ago.
We only need to prove that $$a^{p_{1}p_{2}p_{3}}-b^{p_{1}p_{2}p_{3}}$$ has a prime factor $P>n$. But I can't. Thank you very much!


If $a=b$ then $a^n-b^n=0$ is divisible by any prime, so we are done since there are infinitely many primes.

Otherwise we may WLOG assume $a>b$. Let $d=\gcd(a, b)$. By Zsigmondy's theorem, $\left(\frac{a}{d}\right)^n-\left(\frac{b}{d}\right)^n$ has a prime factor $p$ that does not divide $\left(\frac{a}{d}\right)^k-\left(\frac{b}{d}\right)^k$ for any positive integer $k<n$. (Note $n \not=2, 6$)

We cannot have $p \mid \frac{a}{d}$, for otherwise $p \mid \left(\frac{a}{d}\right)^n-\left(\frac{b}{d}\right)^n$ implies $p \mid \frac{b}{d}$ as well, so $p \mid \frac{a}{d}-\frac{b}{d}$ and $1<n$, a contradiction. Thus $p \nmid \frac{a}{d}$, and simililarly $p \nmid \frac{b}{d}$.

The order of $\left(\frac{a}{d}\right)\left(\frac{b}{d}\right)^{-1} \pmod{p}$ is thus $n$. Since $p \nmid \left(\frac{a}{d}\right)\left(\frac{b}{d}\right)^{-1}$, we have by Fermat's little theorem that $\left(\left(\frac{a}{d}\right)\left(\frac{b}{d}\right)^{-1}\right)^{p-1} \equiv 1\pmod{p}$. Thus $n \mid p-1$. This gives (since clearly $p>1$) that $n \leq p-1$ so $p>n$.

Finally since $a^n-b^n=d^n\left(\left(\frac{a}{d}\right)^n-\left(\frac{b}{d}\right)^n\right)$ we have $p \mid a^n-b^n$ and $p>n$, so we are done.

A simpler proof which does not appeal to Zsigmondy's theorem might be possible, as we only require a special case. (Here $n=p_1p_2p_3$) and may not require the full machinery used to prove Zsigmondy's theorem (Cyclotomic polynomials)

  • $\begingroup$ Nice ! Thank you very much $\endgroup$ – math110 Apr 18 '14 at 4:15

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.