# Find the values of $p$ and $q$

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$$.

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

$$p^2-k^2p+(k+1)=0,$$

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?

• Oh thanks, now I know how to finish it, thanks – Matheus Domingos Oct 6 '18 at 18:55
• 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? – Matheus Domingos Oct 6 '18 at 19:12
• @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$. – Carl Schildkraut Oct 6 '18 at 19:16
• 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$. – Inactive - avoiding CoC Oct 6 '18 at 19:17
• Sorry, I didn't understood how to finish using it – 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}

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.

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