5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why can't they both be odd? That leads to an odd number dividing into an even number, but there is no problem with that. They can't both be even because we would have an even dividing into an odd. $\endgroup$ – Ross Millikan Jul 27 '18 at 16:06
  • $\begingroup$ @Ross Millikan Oops on my part -- you're right. In seeing the most evident odd-even relationship, I lost track of the remaining possibility. My solutions are still solutions, but are not necessarily exhaustive as an answer to the posed question. $\endgroup$ – Keith Backman Jul 27 '18 at 17:28

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.