Finding primes fitting a certain algebraic relation.

[chingel]

Homework Statement

Find all the primes p and q such that [itex]p^2-p-1=q^3[/itex]

The Attempt at a Solution

Trying out the first prime number 2, it is clear that [itex]p>q[/itex] and that the difference is larger than 1. Then when factorizing it [itex]p^2-p=q^3+1[/itex] [itex]\Rightarrow[/itex] [itex]p(p-1)=(q+1)(q^2-q+1)[/itex], I get that p must divide [itex]q^2-q+1[/itex], 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.

 

[Vargo]

q+1 must divide p-1.

 

[chingel]

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

 

[Dick]

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

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?

 

[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

 

[Dick]

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

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

 

[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 [itex]p=k(q+1)+1[/itex] and substitute to get the quadratic for q, what you end up with is [itex]q^2-q(k^2+1)+(1-k^2-k)=0[/itex], from where it is important to notice that q must divide [itex](1-k^2-k)[/itex], or [itex]k^2+k-1=nq[/itex], 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 [itex]q=\frac{nq+2-k+\sqrt{nq(nq+8-2k)+(k-2)^2}}{2}[/itex]. The expression under the radical is larger than [itex](k-2)^2[/itex]. Trying that k=1 or k=2 doesn't work, I then get that [itex]q>\frac{nq}{2}[/itex], which is only possible when n=1. Therefore [itex]k^2+k-1=q[/itex] in addition to the previous relation [itex]q=\frac{k^2+1+\sqrt{k^4+6k^2+4k-3}}{2}[/itex] 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 [itex]q=\frac{nq+2-k+\sqrt{nq(nq+8-2k)+(k-2)^2}}{2}[/itex] and substitute into it n=1 and [itex]k^2=q+1-k[/itex], which turned it into [itex]q=\frac{q+2-k+\sqrt{q^2-2qk+9q-5k+5}}{2}[/itex], which after squaring and substituting for k^2 once more turns it into [itex]4q(k-3)=0[/itex].

 

[Dick]

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 [itex]p=k(q+1)+1[/itex] and substitute to get the quadratic for q, what you end up with is [itex]q^2-q(k^2+1)+(1-k^2-k)=0[/itex], from where it is important to notice that q must divide [itex](1-k^2-k)[/itex], or [itex]k^2+k-1=nq[/itex], 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 [itex]q=\frac{nq+2-k+\sqrt{nq(nq+8-2k)+(k-2)^2}}{2}[/itex]. The expression under the radical is larger than [itex](k-2)^2[/itex]. Trying that k=1 or k=2 doesn't work, I then get that [itex]q>\frac{nq}{2}[/itex], which is only possible when n=1. Therefore [itex]k^2+k-1=q[/itex] in addition to the previous relation [itex]q=\frac{k^2+1+\sqrt{k^4+6k^2+4k-3}}{2}[/itex] 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 [itex]q=\frac{nq+2-k+\sqrt{nq(nq+8-2k)+(k-2)^2}}{2}[/itex] and substitute into it n=1 and [itex]k^2=q+1-k[/itex], which turned it into [itex]q=\frac{q+2-k+\sqrt{q^2-2qk+9q-5k+5}}{2}[/itex], which after squaring and substituting for k^2 once more turns it into [itex]4q(k-3)=0[/itex].

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

 

[ehild]

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

k⁴+6k²+4k-3=(k²+3)²+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 k²+3.

ehild

 

[Dick]

k⁴+6k²+4k-3=(k²+3)²+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 k²+3.

ehild

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

 

[ehild]

The discriminant is monotonously increasing with k, and it is easy to show that can not be the square of natural numbers greater than k²+3.

Suppose there is a natural number x, so as

((k²+3)+x)²=(k²+3)²+4(k-3)
This leads to the quadratic equation in k: 2xk² -4k+(x²+6x+12)=0
The discriminant is D=16-8x(x²+6x+12) which can not be positive if x is a natural number. x must be zero.

ehild

 

[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).

[itex]\frac{p-1}{q+1}=k[/itex], then also [itex]p-1=k(q+1)[/itex] and [itex]p=k(q+1)+1[/itex].

If you substitute p into [itex]p^2-p-1=q^3[/itex], you get [itex]q^2-q(k^2+1)+(1-k^2-k)=0[/itex], from where q must divide [itex]1-k^2-k[/itex], 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 [itex]k^2+k-1=nq[/itex] (switched signs so that n is positive).

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

Now substituting into [itex]q^2-q(k^2+1)+(1-k^2-k)=0[/itex] using [itex]k^2=q+1-k[/itex] and [itex]q=k^2+k-1[/itex][itex]\Rightarrow[/itex] [itex]q^2-q(k^2+1)+(1-k^2-k)=[/itex][itex]q(k^2+k-1)-q(k^2+1)+1-(q+1-k)-k=[/itex]
[itex]q(k^2+k-1)-q(k^2+1)-q=[/itex][itex]q(k^2+k-1-k^2-1-1)=q(k-3)=0[/itex][itex]\Rightarrow[/itex][itex]k=3[/itex]

 

[ehild]

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

That was very clever!

Now substituting into [itex]q^2-q(k^2+1)+(1-k^2-k)=0[/itex] using [itex]k^2=q+1-k[/itex] and [itex]q=k^2+k-1[/itex][itex]\Rightarrow[/itex] [itex]q^2-q(k^2+1)+(1-k^2-k)=[/itex][itex]q(k^2+k-1)-q(k^2+1)+1-(q+1-k)-k=[/itex]
[itex]q(k^2+k-1)-q(k^2+1)-q=[/itex][itex]q(k^2+k-1-k^2-1-1)=q(k-3)=0[/itex][itex]\Rightarrow[/itex][itex]k=3[/itex]

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

ehild

 

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