<s>[INST] Find all pairs of prime numbers $p , q$ for which: $p^2 | q^3 + 1$ and $q^2 | p^6 − 1$. 
Find all pairs of prime numbers $p , q$ for which:
  $$p^2 \mid q^3 + 1 \tag{A}$$
  and
  $$q^2 \mid p^6 − 1 \tag{B}$$

The question is from the Bulgaria National Olympiad 2014.
I'm looking for any solution I may have missed, and generally any alternative method that might reduce the case work (could combine cases 2.1 and 3.1, I suppose).

I will split the work into three cases:


*

*$p=q\ge2$. 

*$p>q\ge2$.

*$q>p\ge2$.


Case 1
It is clear that neither (A) nor (B) are met.
Case 2
First consider two subcases:


*

*$p>q$ and $q\in\{2,3\}$.

*$p>q\ge5$.


Case 2.1
$$\begin{align}
q=2 &\implies p^2\mid9  &\implies p^2=9 &\implies p=3 \\
q=3 &\implies p^2\mid28 &\implies p^2=4 &\implies\text{ no solution} \\
\end{align}$$
So $\boxed{(p,q)=(3,2)}$ is the only solution for this case.
Case 2.2
(A) factorises as $p^2 \mid (q+1)(q^2-q+1)$. Now
$$q^2-q+1=(q+1)(q-2)+3 \implies \gcd(q+1,q^2-q+1)=
\begin{cases} 3,\quad\text{if }3\mid q+1\\1,\quad\text{otherwise}\end{cases}$$
Since $p>5$ is prime, we must have either $p^2\mid q+1$ or $p^2\mid q^2-q+1$. But this is impossible because $p>q\ge5 \implies p^2>q+1\text{ and }p^2>q^2>q^2-q+1$. So there are no solutions here.
Case 3
Consider two subcases:


*

*$q>p$ and $p\in\{2,3\}$.

*$q>p\ge5$.


Case 3.1
$$\begin{align}
p=2 &\implies q^2\mid63 &\implies q^2=9 &\implies q=3 \\
p=3 &\implies q^2\mid728 &\implies q^2=4 &\implies\text{ no solution} \\
\end{align}$$
So $\boxed{(p,q)=(2,3)}$ is the only solution for this case.
Case 3.2
(B) factorises as $q^2 \mid (p^3+1)(p^3-1)$. Now
$$p^3+1=(p^3-1)+2 \implies \gcd(p^3+1,p^3-1)=
\begin{cases} 2,\quad\text{if }p\text{ is odd}\\1,\quad\text{otherwise}\end{cases}$$
Since $q>5$ is prime, we must have either $q^2\mid p^3+1$ or $q^2\mid p^3-1$. If $q^2\mid p^3+1$, the the same arguments as in case 2.2 can be applied to show that $q^2\mid p+1$ or $q^2\mid p^2-p+1$ neither of which is possible when $q>p$.  
So the only remaining possibility is $q^2\mid p^3-1$. This factorises as $q^2\mid (p-1)(p^2+p+1)$. Now
$$p^2+p+1=(p-1)(p+2)+3 \implies \gcd(p-1,p^2+p+1)=
\begin{cases} 3,\quad\text{if }3\mid p-1\\1,\quad\text{otherwise}\end{cases}$$
Since $q>5$ is prime, we must have either $q^2\mid p-1$ or $q^2\mid p^2+p+1$. But this is impossible because $q>p\ge5 \implies q^2>p-1\text{ and }q^2\ge (p+1)^2=p^2+2p+1>p^2+p+1$. So there are no solutions here either.
 [/INST] Here is a shorter solution.  If $p=2$, then $q^2\mid p^6-1=63$ implies that $q=3$.  If $p=3$, then $q^2\mid 3^6-1=728$ leads to $q=2$.  If $q=2$, then $p^2\mid q^3+1=9$ means $p=3$.  If $q=3$, then $p^2\mid q^3+1=28$ gives $p=2$.  That is, solutions with $p\leq 3$ or $q\leq 3$ are $(p,q)=(2,3)$ and $(p,q)=(3,2)$.  From now on, suppose that $p,q>3$.
Observe that $p-1$, $p+1$, $p^2-p+1$, and $p^2+p+1$ are pairwise coprime integers.  Thus, $$q^2\mid p^6-1=(p-1)(p+1)(p^2-p+1)(p^2+p+1)$$ implies that $q^2$ divides one of the four numbers $p-1$, $p+1$, $p^2-p+1$, and $p^2+p+1$.  First, we assume that $q^2$ divides either $p-1$ or $p+1$.  Then,
$$q^2\leq p+1\text{ so that }q<p\,.$$
Now, from $p^2\mid q^3+1=(q-1)(q^2-q+1)$ and $q-1$ is relatively prime to $q^2-q+1$, then $$p^2\mid q-1\text{ or }p^2\mid q^2-q+1\,,\tag{*}$$ but this is impossible as $q<p$.  Hence, $q^2$ must divide either $p^2-p+1$ or $p^2+p+1$.
Now, we have $$q^2\leq p^2+p+1<(p+1)^2\,,\text{ whence }q\leq p\,$$
Again, from (*), we obtain
$$p^2\leq q^2-q+1 <q^2\leq p^2\,,$$
which is a contradiction.  Hence, there are no other solutions than the two listed in the first paragraph.
</s>