# 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:

1. $p=q\ge2$.
2. $p>q\ge2$.
3. $q>p\ge2$.

## Case 1

It is clear that neither (A) nor (B) are met.

## Case 2

First consider two subcases:

1. $p>q$ and $q\in\{2,3\}$.
2. $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:

1. $q>p$ and $p\in\{2,3\}$.
2. $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.

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.
The insight to simplify is that $p$ and $q$ must have different parities; they can't both be odd. At least one of them must be odd, because there are not two even primes. Then the other one must be even, because the addition or subtraction of $1$ makes one of the compound expressions even. Hence one of them must be 2. If we choose $p=2$, then $p^6-1=63$ and $q=3$. This checks out because $4\mid28$. If $q=2$, then $q^3+1=9$ and $p=3$. This checks out because $4\mid728$. $(p,q)=(2,3)$ in either order.