### Friday, March 27, 2009

## JSH: Wacky quadratic residues result

Ok, so finding variants that will solve Pell's Equation, gave me a result I think is kind of wacky, which is that EVERY prime number must have 2, -1, or -2 as a quadratic residue.

Is that previously known? If so, what is the prior proof?

I've noted it's true from the result that for every solution to x^2 - Dy^2 = 1, where D is a prime number there must also exist a solution to exactly one variant as follows:

j^2 - Dk^2 = 2 where k = sqrt((x-1)/D) and j = sqrt(x+1)

or

j^2 - Dk^2 = -2 where k = sqrt((x+1)/D) and j = sqrt(x-1)

or

j^2 - Dk^2 = - 1 where k = sqrt((x+1)/2D) and j = sqrt((x-1)/2)

And that means that for at least one of those cases when D is a prime, D must have 2, -2 or -1 as a quadratic residue.

Interestingly, if D is a composite and NONE of those variants are true, then a solution to Pell's Equation will non-trivially factor D.

I'm curious if anyone can find old research results which cover any of these areas.

Of special curiosity would be the method used to prove—if they exist in the literature—where my curiosity is mostly sparked by the 2, -2, or -1, quadratic residue result for primes.

Is that previously known? If so, what is the prior proof?

I've noted it's true from the result that for every solution to x^2 - Dy^2 = 1, where D is a prime number there must also exist a solution to exactly one variant as follows:

j^2 - Dk^2 = 2 where k = sqrt((x-1)/D) and j = sqrt(x+1)

or

j^2 - Dk^2 = -2 where k = sqrt((x+1)/D) and j = sqrt(x-1)

or

j^2 - Dk^2 = - 1 where k = sqrt((x+1)/2D) and j = sqrt((x-1)/2)

And that means that for at least one of those cases when D is a prime, D must have 2, -2 or -1 as a quadratic residue.

Interestingly, if D is a composite and NONE of those variants are true, then a solution to Pell's Equation will non-trivially factor D.

I'm curious if anyone can find old research results which cover any of these areas.

Of special curiosity would be the method used to prove—if they exist in the literature—where my curiosity is mostly sparked by the 2, -2, or -1, quadratic residue result for primes.