If $p^3+p=q^2+q$ where $p$ and $q$ are prime numbers, Find all the solutions (p, q)

I tried to solve this exercise using that:

$p^2 = -1(\text{mod} \, q)$ and $q = -1(\text{mod} \, p)$; So: $q+1=ap$ and $p^2+1=bq$, where $b$ and $q$ integers.

Then I tried to solve a quadratic equation, but I could not finish the problem


Clearly $p\neq q$, and because $p$ and $q$ are prime and $$p(p^2+1)=p^3+p=q^2+q=q(q+1),$$ we must have $p\mid q+1$ and $q\mid p^2+1$. Write $$q+1=ap\qquad\text{ and }\qquad p^2+1=bq,$$ to find that $p^2-abp+b+1=0$. In particular $b+1\equiv0\pmod{p}$, say $b=cp-1$, but then $$p^2+1=(cp-1)q=(cp-1)(ap-1)=acp^2-(a+c)p+1.$$ Note that $a$, $b$ and $c$ are positive integers, and that $a>1$ as otherwise $p=q+1$ which implies that $(p,q)=(3,2)$ which is not a solution. The equation above simplifies to $$(ac-1)p=a+c,$$ and as $p\geq2$ clearly we cannot have $a,c\geq2$. Hence $c=1$ and so $$p^2+1=bq=(cp-1)q=(p-1)q.$$ In particular $p-1\mid p^2+1$. As $p-1\mid p^2-1$ it follows that $p-1=2$, so $p=3$ and hence $q=5$.

  • $\begingroup$ How do I finish this solution? Finding all the solution? $\endgroup$ – Matheus Domingos Oct 6 '18 at 19:05
  • $\begingroup$ @MatheusDomingos I completed the solution for you. $\endgroup$ – Inactive - avoiding CoC Oct 6 '18 at 19:05
  • 1
    $\begingroup$ Thank you, now I understood the limitation. I need to have a+c=>ac-1... What implies that (a-1)(c-1)=>2. Thanks $\endgroup$ – Matheus Domingos Oct 6 '18 at 19:11
  • 1
    $\begingroup$ I rearranged the argument a bit, as in fact $a>1$ follows very easily earlier on, simpifying the final step. $\endgroup$ – Inactive - avoiding CoC Oct 6 '18 at 19:12
  • $\begingroup$ Understood, more elegant this way,thanks again $\endgroup$ – Matheus Domingos Oct 6 '18 at 19:14

$$p^3+p=q^2+q \implies p|q^2+q \implies p|q\ \mathrm{or}\ p|(q+1).$$

Obviously, $p\neq q$, so $p\nmid q$. Thus, we can set $q=kp-1$. This then reduces to


which has an integer solution iff $k^4-4k-4$ is a square. Can you see why this is not the case for large $k$, and determine the solutions from there?

  • $\begingroup$ Oh thanks, now I know how to finish it, thanks $\endgroup$ – Matheus Domingos Oct 6 '18 at 18:55
  • $\begingroup$ Is there a better way to do that? I learned in high school to solve that using k^4-4k-4=a^2 and then I have to study that. Is there a better way to do that? $\endgroup$ – Matheus Domingos Oct 6 '18 at 19:12
  • $\begingroup$ @MatheusDomingos Note that $k^4-4k-4$ is very close to $(k^2)^2$. Specifically, for most positive $k$, it is between $(k^2-1)^2$ and $k^2$. $\endgroup$ – Carl Schildkraut Oct 6 '18 at 19:16
  • 1
    $\begingroup$ Note that $k^4=(k^2)^2$ is a square, and that the previous square is $$(k^2-1)^2=k^4-2k^2+1,$$ which is smaller than $k^4-4k-4$ whenever $2k^2-1>4k+4$, and so the latter cannot be a square unless $2k^2-1\leq 4k+4$. $\endgroup$ – Inactive - avoiding CoC Oct 6 '18 at 19:17
  • $\begingroup$ Sorry, I didn't understood how to finish using it $\endgroup$ – Matheus Domingos Oct 6 '18 at 19:24

Hint: Since $p$ divides $p^3+p$, also $p$ divides $q(q+1)$, hence $p$ either divides $q$ or $p$ divides $q+1$, because $p$ is prime. Can you finish it?


Remember that if $a,b$ are positive integers such that $a\mid b$ then $a\leq b$. I'll be using this frekvently here.

From $$p(p^2+1)= q(q+1)\implies p\mid q\;\;\;{\rm or}\;\;\;p\mid q+1$$

1. case $p\mid q$, then $q+1\mid p^2+1$. Write $q+1=s$ then we get $$ps\mid (p^2+1)(s-1) = p^2s-p^2+s-1\implies ps\mid p^2-s+1$$

Since $p^2+1\geq s$ we have 2 subcases:

1.1 case $p^2+1>s$, then $ps\leq p^2-s+1$ so $s(p+1)\leq p^2+1$, and thus $$s\leq {p^2+1\over p+1} <p\implies s\leq p-1$$

So $q+1\leq p-1 \leq q-1$ and thus no solution.

1.2 case $p^2+1=s$, then $q^2+1 = q+1$ and again no solution.

2. case $p\mid q+1$, then $q\mid p^2+1$. Then we get $$pq\mid (p^2+1)(q+1) = p^2q+p^2+q+1\implies pq\mid p^2+q+1$$

so we have $pq\leq p^2+q+1$ so $q \leq {p^2+1\over p-1} \leq p+2$ if $p\geq 3$. So if $p\geq 3$ and since $p\mid q$ that $q\in \{p,p+1,p+2\}$ which is easy to finish by hand.

  • $\begingroup$ Thanks, got this solution! $\endgroup$ – Matheus Domingos Oct 6 '18 at 19:25

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.