# Finding primes fitting a certain algebraic relation.

1. Dec 20, 2012

### chingel

1. The problem statement, all variables and given/known data
Find all the primes p and q such that $p^2-p-1=q^3$

3. The attempt at a solution
Trying out the first prime number 2, it is clear that $p>q$ and that the difference is larger than 1. Then when factorizing it $p^2-p=q^3+1$ $\Rightarrow$ $p(p-1)=(q+1)(q^2-q+1)$, I get that p must divide $q^2-q+1$, since p is larger than q+1. However, these are all the observations I have made and I don't have a good idea how to continue. Hints are welcomed.

With some testing with my computer, I found a solution with 11 and 37 and no others in near sight.

2. Dec 20, 2012

### Vargo

q+1 must divide p-1.

3. Dec 20, 2012

### chingel

I tried taking p=k(q+1)+1, then I got a quadratic for q which gave me $q=\frac{k^2+1+\sqrt{k^4+6k^2+4k-3}}{2}$, from where I can notice that 3 is a working solution, giving q=11, but I'm not sure how to move forward.

4. Dec 20, 2012

### Dick

What course are you taking or where did you find this problem? What you've got there is a elliptic curve in p and q. This subject is way beyond me, but smarter persons than I am can sometimes prove there are only a finite number of rational solutions. But the whole subject is not at all elementary. I've been groping around trying to find an easy approach and I'm about ready to give up. Any reason to believe there is one?

Last edited: Dec 21, 2012
5. Dec 21, 2012

### chingel

It should be a high school olympiad type problem. I got it on paper, but I was able to find a reference of it online, problem 4 at the beginning:

http://www.math.ust.hk/excalibur/v17_n2.pdf

6. Dec 21, 2012

### Dick

Ok, so there must be a clever way that doesn't use any big guns. That's good to know.

7. Dec 23, 2012

### chingel

I got some clues from the person I got the problem from and I was then able to solve it. The key was that after you take $p=k(q+1)+1$ and substitute to get the quadratic for q, what you end up with is $q^2-q(k^2+1)+(1-k^2-k)=0$, from where it is important to notice that q must divide $(1-k^2-k)$, or $k^2+k-1=nq$, where n is some integer. If I then substitute for k^2 in the big formula I got for q in the last post from the quadratic, I get $q=\frac{nq+2-k+\sqrt{nq(nq+8-2k)+(k-2)^2}}{2}$. The expression under the radical is larger than $(k-2)^2$. Trying that k=1 or k=2 doesn't work, I then get that $q>\frac{nq}{2}$, which is only possible when n=1. Therefore $k^2+k-1=q$ in addition to the previous relation $q=\frac{k^2+1+\sqrt{k^4+6k^2+4k-3}}{2}$ and solving those two the only working solution is k=3, so the only primes are q=11 and p=37.
Instead of solving the third degree polynomial, I found it easier to use $q=\frac{nq+2-k+\sqrt{nq(nq+8-2k)+(k-2)^2}}{2}$ and substitute into it n=1 and $k^2=q+1-k$, which turned it into $q=\frac{q+2-k+\sqrt{q^2-2qk+9q-5k+5}}{2}$, which after squaring and substituting for k^2 once more turns it into $4q(k-3)=0$.

8. Dec 23, 2012

### Dick

Yep. That's sounds like an Olympiad solution alright. Nice job and thanks a lot for posting back!

9. Dec 24, 2012

### ehild

k4+6k2+4k-3=(k2+3)2+4(k-3). It has to be perfect square and it is when k=3. The discriminant is monotonously increasing with k, and it is easy to show that can not be the square of natural numbers greater than k2+3.

ehild

10. Dec 24, 2012

### Dick

Now that solution I like! I figured it out how it worked a lot faster than the other one. Bravo.

11. Dec 24, 2012

### ehild

Suppose there is a natural number x, so as

((k2+3)+x)2=(k2+3)2+4(k-3)
The discriminant is D=16-8x(x2+6x+12) which can not be positive if x is a natural number. x must be zero.

ehild

12. Dec 24, 2012

### chingel

Thanks for the nice solution ehild.

Another solution, that doesn't solve a quadratic equation, based on an idea suggested to me (not my idea).

$\frac{p-1}{q+1}=k$, then also $p-1=k(q+1)$ and $p=k(q+1)+1$.

If you substitute p into $p^2-p-1=q^3$, you get $q^2-q(k^2+1)+(1-k^2-k)=0$, from where q must divide $1-k^2-k$, because when you divide the whole quadratic expression by q, the first term in the sum is an integer, the second is an integer and for the whole sum to be an integer, zero, the third must also be an integer, therefore $k^2+k-1=nq$ (switched signs so that n is positive).

Now from $q^3=p^2-p-1>(p-1)^2=k^2(q+1)^2>k^2q^2$, where I substituted (p-1) from above. Then $q>k^2$, also $2q>2k^2>k^2+k-1$. Since $k^2+k-1=nq$$\Rightarrow$ $2q>nq$$\Rightarrow n=1$, so $k^2+k-1=q$, in addition to the previous $q^2-q(k^2+1)+(1-k^2-k)=0$.

Now substituting into $q^2-q(k^2+1)+(1-k^2-k)=0$ using $k^2=q+1-k$ and $q=k^2+k-1$$\Rightarrow$ $q^2-q(k^2+1)+(1-k^2-k)=$$q(k^2+k-1)-q(k^2+1)+1-(q+1-k)-k=$
$q(k^2+k-1)-q(k^2+1)-q=$$q(k^2+k-1-k^2-1-1)=q(k-3)=0$$\Rightarrow$$k=3$

13. Dec 24, 2012

### ehild

That was very clever!

I would substitute k2+k-1=q, so the quadratic equation for q becomes q2-(k2+1)q-q=0, that is q2-(k2+2)q -> q=k2+2.
q=k2+k-1=k2+2 ->k=3.:tongue2:

ehild

14. Dec 24, 2012

### chingel

All the credit for the clever way of getting n=1 goes to the person who gave me the problem, I just shared it here.

Yes the other substitution is better, more clear and direct, I guess I have a weird inclination to always try to substitute for k^2 in this problem, heh, as it got me something I could work with under the square root previously.