Number Busters

The answer is 4998. Obviously $(3,3,n)$ is a solution where $n=2,3,4,...$ . But are there any other solutions? Assume there exist solutions such that $p$ and $q$ are distinct and $p,q>3$ . We can assume that $q>p \geq 5$ .

If $n=2$ , then $q^2|p^4-3^4$ , namely $q^2|(p^2+3^2)(p^2-3^2)$ . Since $q$ cannot divide $p^2+3^2$ and $p^2-3^2$ at the same time, $q^2$ divides only one of $p^2+3^2$ and $p^2-3^2$ . However, $0<p^2-3^2<q^2$ , $p^2+3^2(not)(equal)(to)q^2$ and $p^2+3^2<2p^2<2q^2$ , a contradiction. Hence there is no solution for $n=2$ . So, we can assume that $n \geq 3$ , then $p^n|q^(n+2)-3^(n+2)$ and $q^n|p^(n+2)-3^(n+2)$ . $\gcd(p^n,q^n)=1$ yields $p^nq^n|p^(n+2)+q^(n+2)-3^(n+2)$ hence $p^nq^n \leq p^(n+2)+q^(n+2)-3^(n+2)<2q^(n+2)$ so, we have $p^n<q^2$ .

On the other hand, $q^n|p^(n+2)-3^(n+2)$ implies $q^n<p^(n+2)$ . So, $q<p^(1+\frac{2}{n})$ . Combining it with $p^n<2q^2$ then yields $p^n<2p^(2+\frac{4}{n})<p^(3+\frac{4}{n})$ , therefore $n<3+\frac{4}{n}$ , namely $n=3$ . Thus, $p^3|q^5-3^5$ and $q^3|p^5-3^5$ .

Since $5^5-3^5=2 \times 11 \times 131$ which does not contain factors of the form $q^3$ , so $p>5$ . $p^3|q^5-3^5$ implies that $p|q^5-3^5$ , and Fermat's Little Theorem yields $p|q^(p-1)-3^(p-1)$ . When $(5,p-1)=1$ and $p(not)(divide)q-3$ , then $\frac{q^5-3^5}{q-3},\frac{q^(p-1) -3^(p-1)}{q-3} \geq p>1$ . However, for example, if $p-1=5k+4$ , then $(\frac{q^5-3^5}{q-3},\frac{q^(p-1) -3^(p-1)}{q-3})$ = $(q^4+q^3.3+...+q.3^3+3^4, q^(p-2)+q^(p-3).3+...+q.3^(p-3)+3^(p-2$ = $(q^4+q^3.3+...+q.3^3+3^4,q^(p-2)+q^(p-3).3+q^(p-4).3^2+q^(p-5).3^3)$ = $(q^4+q^3.3+...+q.3^3+3^4, q^(p-6).3^4)$ = $(q^4+q^3.3+...+q.3^3+3^4,q^(p-7))$ =...= $(q^4+q^3.3+...+q.3^3+3^4,3^4)=1$

and the same result can also be obtained for $p-1=5k+r,r=1,2,3.$ . Thus, $p|q-3$ if $(5,p-1)=1$ , i.e. $q \equiv 3 \pmod p$ . Then $\frac{q^5-3^5}{q-3}=q^4+3q^3+...+3^4 \equiv 5 \times 3^4 (not)(congruent) 0\pmod p$ hence $p^3|q-3$ . However, $q^3|p^5-3^5$ gives $q^3 \leq p^5-3^5<p^5=(p^3)^\frac{5}{3}<q^\frac{5}{3}$ , a contradiction. Similar contradiction is obtained if $(5,q-1)$ =1.

Thus, we assume that $(5,p-1)=(5,q-1)=5$ . $(q,p-3)=1$ (since $q>p \geq 7$ ) and $q^3|p^5-3^5$ implies that $q^3|\frac{p^5-3^5}{p-3}$ , hence $q^3 \leq \frac{p^5-3^5}{p-3}=p^4+p^3.3+p^2.3^2+p.3^3+3^4$ . $5|p-1 and 5|q-1$ implies that $p \geq 11, q \geq 31$ . Therefore $q^3 \leq p^4(1+\frac{3}{p}+(\frac{3}{p})^2+(\frac{3}{p})^3+(\frac{3}{p})^4)<p^4.(1-\frac{3}{p})^-1 \leq \frac{11}{8}p^4 ,$ hence $(\frac{q}{p})^3 \leq \frac{11}{8}p$ and $\frac{q^2}{p^3}=((\frac {q}{p})^3)^\frac{2}{3}.\frac{1}{p} \leq (\frac {11}{8})^\frac{2}{3}.p^\frac{-1}{3}<\frac{5}{8}$ . Thus, $\frac{p^5+q^5-3^5}{p^3q^3} < \frac{p^2}{q^3}+\frac{q^2}{p^3}<\frac{1}{31}+\frac{5}{8}<1,$ which is a contradiction. Thus the solutions are $(3,3,n),n=2,3,4,...$ . Since it is given that $1<n<5000,n=2,3,4,...4999$ . So, there are a total of $\boxed{4998}$ solutions.