Find all pairs $(p,q)$ of prime numbers such that $$ p(p^2 - p - 1) = q(2q + 3) .$$
Problem
Source: Croatia TST 2016
Tags: number theory, Diophantine equation, prime numbers, primes
27.04.2016 23:01
Hello. My solution. If $p=q$ then $p^2-p-1=2p+3\Leftrightarrow p^2-3p-4=0\Leftrightarrow (p+1)(p-4)=0$,thus we don't have any solutions. If $p\neq q$ then $p\mid 2q+3$.Suppose that $2q+3=kp$ for some positive integer $k$.The equation is equivalent to $p(p^2-p-1)=\frac{kp-3}{2}kp\Leftrightarrow 2(p^2-p-1)=k(kp-3)\Leftrightarrow 2p^2-p(k^2+2)+3k-2=0$. $\Delta =(k^2+2)^2-8(3k-2)$ and we want this to be a perfect square.However,for $k\geq 11$ it is easy to verify that $(k^2+1)^2<\Delta <(k^2+2)^2$.Thus,$k\leq 10$.From now on,the problem becomes a mere case analysis. $\bullet$ If $k=10$ then $\Delta =102^2-8\cdot 28=10180$ which isn't a perfect square. $\bullet$ If $k=9$ then $\Delta \equiv 20\equiv 2\pmod 3$ which isn't perfect square. $\bullet$ If $k=8$ then $\Delta =66^2-8\cdot 22=4180$ which isn't perfect square. $\bullet$ If $k=7$ then $\Delta =51^2-8\cdot 19=2449$ which isn't perfect square. $\bullet$ If $k=6$ then,again $\Delta \equiv 2\pmod 3$,thus no solutions. $\bullet$ If $k=5$ then $\Delta =625$ and we obtain the pair $(p,q)=(13,31)$. $\bullet$ If $k=4$ then $\Delta =18^2-80=244$ which isn't a perfect square. $\bullet$ If $k=3$ then $\Delta \equiv 2\pmod 3$,hence we get no solutions. $\bullet$ If $k=2$ then $\Delta =4$,but there are no solutions. $\bullet$ If $k=1$ then $\Delta =1$ but there are no solutions.
14.01.2017 00:21
Case $p=q$ $p(p^2 -p -1) = p(2p+3) \Leftrightarrow (p-1)(p+4) = 0$ Since $p=1$ and $p=-4$ aren't prime, it follows that $p \neq q$ $p \neq q \implies p \vert 2q+3 $ and $q \vert p^2 -p -1 \implies pq \vert (2q+3)(p^2-p-1) \implies pq \vert 2p^2 q -2pq-2q+3p^2-3p-3 \implies pq|3p^2 - 3p - 3 - 2q$ $q \vert p^2-p-1 \implies q \leq p^2-p-q \implies 3p^2-3p-3-2q >0$ $pq \vert 3p^2-3p-3-2q \implies 3p^2 - 3p -3 \geq pq + 2q$ For $p \leq (2q+3)/7 \Leftrightarrow q \geq (7p-3)/2$ $3p^2 - 3p -3 \geq pq + 2q \implies 3p^2-3p-3 \geq p(7p-3)/2 + 7p-3 \Leftrightarrow 0 \geq p^2 + 17p \Rightarrow\Leftarrow$ therefore $p>(2q+3)/7$ We have $p \in \{(2q+3)/6,(2q+3)/5,(2q+3)/4,(2q+3)/3,(2q+3)/2 \}$ We can cross of $(2q+3)/6$, $(2q+3)/4$, $(2q+3)/2$ because $2q+3$ is odd. If $3 \vert 2q+3$ We have $3 \vert q \implies q = 3$ $p(p^2 -p -1) = 27 \implies p=3 \Rightarrow\Leftarrow$ because $p \neq q$ Therefore $2q+3$ is not divisible by $3$ so we can also cross it off. Now we only have $p = (2q+3)/5$ which after plugging in $p(p^2 -p -1) = q(2q+3)$ and solving the quadratic equation yields $(p,q) = (13,31)$
25.09.2019 15:36
Another mass collaborative solution (Anushka Aggarwal, Paul Hamrick, Aditya Khurmi, Samuel Wang, Tim Qian, Derek Liu, Valentio Iverson, Gene Yang, Mason Fang, Easton Singer, et al) --- the answer is $(p,q) = (13,31)$ which works, so we now show there are no more solutions. It's easy to check there are no solutions for $\min(p,q) \le 3$, so we henceforth assume $\min(p,q) > 3$. Then we have $\gcd(p, p^2-p-1) = \gcd(q,2q+3) = 1$. If $p=q$ then $p^2-p-1 = 2p+3 \iff p^2-3p-4 = 0$ and we get a clear contradiction. So assume now that $p \mid 2q+3$, and also $q \mid p^2-p-1$. Let $2q+3 = kp$ with $k$ odd; we now get \[ (p^2-p-1) = k \cdot \frac{kp-3}{2}. \]Viewed as a quadratic in $p$, the discriminant (which must be the square of a rational number) is \[ \Delta = \left( \frac{k^2}{2}+1 \right)^2 - 4\left( \frac32 k - 1 \right). \]Note that in fact $4\Delta$ should be an odd square. However, consider the assertion \[ \left( k^2+1 \right)^2 < 4\Delta < \left( k^2+3 \right)^2 \qquad(\ast) \]The right inequality is always true and the left inequality holds for $6k-4 < (k^2+3/2)(1/2) \iff 24k - 16 < 2k^2+3$ or $2(k-6)^2 = 2k^2-24k + 72 > 53 \iff k > 11$. Thus when $k > 11$ the relation $(\ast)$ and contradicts the fact that $4\Delta$ should be an odd square. So remains to bash $k \le 11$. As $2q = kp-3$ and $q > 3$, we may assume $3 \nmid k$, and so need to check $k \in \{1,5,7,11\}$. Computing the values of $\Delta$ for these $k$ gives the following cases: If $k=1$ then $\Delta = 9/4-2 = 1/4$ \[ p^2-p-1 = \frac{p-3}{2} \iff 2p^2 - 3p + 1 = 0 \] If $k=5$ then $\Delta = 729/4 - 26 = 625/4$ \[ 2p^2-27p+13 = 0 \implies p=13. \]This gives solution $(p,q) = (13,31)$. If $k=7$ then $\Delta = \frac{2601-152}{4} = \frac{2449}{4}$ which is not a square. $k=11$ then $\Delta = \frac{15129-248}{4} = \frac{14881}{4}$, which is not a square. This concludes the proof.
13.07.2021 11:39
Call a rational number $r$ beautiful if $2r$ is integer. One can easily check that $p\neq q$, $p\neq 2$ and $q\neq 2$. So, obviously $p$ divides $2q+3$. Let $\frac{2q+3}{p}=k$ for some positive integer $k$ which implies, $q=\frac{kp-3}{2}$. Setting the value into the equation gives, $$p^2-p-1=\frac{k(kp-3)}{2}$$$$\Rightarrow 2p^2-2p-2=k^2p-3k$$$$\Rightarrow 2p^2-p(k^2+2)+(3k-2)=0$$$$\Rightarrow p^2-p\frac{k^2+2}{2}+\frac{3k-2}{2}=0$$Now the quadratic equation has atleast a prime solution. So, the other root must be a beautiful number. This implies $p$ divides $3k-2$. Now maximum sum of the root is $3k-2+\frac{1}{2}$ So, $$3k-2+\frac{1}{2} \geq \frac{k^2+2}{2}$$$$\Rightarrow k^2-6k+5\leq 0$$$$\Rightarrow k\leq 5$$ Now one can easily check that for $k=1,2,3,4$ there do not exist any prime $p$. For $k=5$ we get $p=13$ and leads us to $q=32$. So the only solution in $(p,q)=(13,31)$.
20.06.2022 16:40
A slightly different(possibly shorter) solution: $ p(p^2 - p - 1) = q(2q + 3) .$ We easily get that $p=q$ yields no solutions. This means that $ p\vert 2q+3$ and $q\vert p^2-p-1 (*) $ Now, we have $2q=pl-3$ for some integer $l$ From $ (*) $ we have that $2q\vert 2p^2-2p-2$ which is the same as $pl-3\vert 2p^2 - 2p - 2 \implies pl-3\vert 2p^2 l - 2pl - 2l \implies pl-3\vert 2p(pl-3)-(2pl + 2l - 6p) \implies pl-3\vert 2pl + 2l - 6p$ $\implies pl-3\vert 2(pl-3)+2l-6p+6 \implies pl-3\vert 2l-6p+6$ which means that $pl-3 \leq |2l-6p+6|$. The first case: $pl-3\leq 2l-6p+6$ rearranges to: $(p-2)(l+6)\leq -3$ Which is clearly not true. The second case:$pl-3\leq 6p-2l-6 $ rearranges to: $(l-6)(p+2)\leq -15$ So we have that $l<6$ The rest is just checking the values for $l$ and we substitute to get the needed solutions
31.01.2024 00:44
Solved with brainfertilzer. The only solution is $\boxed{(13,31)}$, which works. Now we prove it's the only solution. Clearly $p\mid 2q + 3$ and $q\mid p^2 - p - 1$. Let $n \cdot p = 2q + 3$ and $n \cdot q = p^2 - p - 1$. So $n$ is odd. We have $n \cdot p = 2 \cdot \frac{p^2 - p - 1}{n} + 3$, so multiplying both sides by $n$ gives that $n^2 p = 2 (p^2 - p - 1) + 3n$, so simplifying gives \[ 2p^2 - (n^2 + 2) p + (3n-2) = 0\]The discriminant of this equation, which is $n^4 + 4n^2 - 24n + 20$, must be a perfect square. However, for $n > 5$, it is strictly in between $(n^2)^2$ and $(n^2 + 2)^2$, so it must be $(n^2 +1)^2$, but this is impossible since $n^4 + 4n^2 - 24n + 20$ has the same parity of $n$, while $(n^2 + 1)^2$ is of the opposite parity. Hence, $n \le 5$. Checking $n\in \{1,3,5\}$ gives that $n=3$ doesn't work, so $n\in \{1,5\}$. If $n = 1$, then $2p^2 - 3p + 1 = 0$, so $p = 1$ or $p = \frac 12$, both are absurd. If $n = 5$, then $2p^2 - 27p + 13 = 0$, so $p = \frac 12$ or $p = 13$. Since $p$ is an integer, it must be equal to $13$. Then, $2q + 3 = 13\cdot 5\implies q = 31$.