## Re: qfbsolve exercise

Expand Messages
• ... Not the square root. Think Chinese: since p is a semiprime, there are *two* essentially different square roots, not related by an overall change of sign.
Message 1 of 4 , Oct 4, 2010
Kermit Rose <kermit@...> wrote:

> > Exercise: Find two pairs of positive integers (x,y) such that
> > 5*x^2 + 5*x*y + y^2 = (137^137 + 1992)*(137^137 + 3464)

> Thank you.
> Now it is clear that 5 is indeed a quadratic residue of
> p = (137^137 + 1992)*(137^137 + 3464)
> And therefore, once we find the sqrt(5) mod p ...

Not "the" square root. Think Chinese: since p is a
semiprime, there are *two* essentially different square
roots, not related by an overall change of sign. You should
use Tonelli-Shanks for these square roots, if you want to do
it all by yourself, which is of course the best way to learn.
And then you may use powers of the square of the unit
(1 + sqrt(5))/2 to shift solutions to the required region with
x > 0 and y > 0. More efficiently, you may use an Euclidean
algorithm to do this, as per Cornacchia-Smith, in Cohen 1.5.2,
or CP 2.3.12.

Best regards

David
Your message has been successfully submitted and would be delivered to recipients shortly.