Proof of Prime & Congruences: Solving x^2\equiv -2 \mod p

[kingwinner]

"Let p be a prime such that there exists a solution to the congruence $$x^2\equiv - 2\mod p$$.
THEN there are integers a and b such that $$a^2 + 2b^2 = p$$ or $$a^2 + 2b^2 = 2p$$."
============================

I don't see why this is true. How can we prove this using basic concepts?
We know that there exists some integer x such that p|(x² -2), what's next?

Any help is appreciated!

 

[JSuarez]

I don't know any elementary proof: they all use concepts like quadratic reciprocity, factorizarion on structures like $\mathbb Z\left[\sqrt{-2}\right]$.

The starting point is that, if you have $a^2 + 2b^2$, you may factorize this expression in $\mathbb Z\left[\sqrt{-2}\right]$ as $\left(a+\sqrt{-2}b\right)\left(a-\sqrt{-2}b\right)$; then you must investigate if p is also factorizable in this domain. Frankly, I think the proof is too advanced for you, but I can point you to documents where it's done (it's a bit long).

 

[CRGreathouse]

Is there a proof with just QR? There may well be a decent elementary proof of QR -- I don't know of one, but it's one of the most-proved theorems in the history of... well... theorem-proving.

 

[JSuarez]

Try reading this document:

http://math.uga.edu/~pete/4400quadrings.pdf"

 

[CRGreathouse]

I don't think that's accessible for the OP.

 

[JSuarez]

It's the most acessible I found online. If anyone knows a simpler proof (even Fermat's original proof), I also would like to see it.

 

[CRGreathouse]

It's the most acessible I found online. If anyone knows a simpler proof (even Fermat's original proof), I also would like to see it.

It's the most accessible I've seen as well -- good find. I just think that the OP's request is probably impossible to fulfill.

 

[robert Ihnot]

It seems like there is too much theory and lose ends to easily handle this. A very, very modest contribution is to notice that if (read X^2 congruent to -2) X^2 ==-2 Mod P, then we have integers a/b = X, (a,b not 0) such that a^2+2b^2 = kp. Furthermore we can allow b to run through all the terms b=1, 2, 3...(p-1)/2 for a series of such equations, of which some would be found to be minimal in the series.

As a matter of fact this is a rather good way to find a solution. Since we are working with squares we can exchange a with p-a, if this results in a smaller solution. For example p=19, then we can choose X to be 6. A series of solutions then is (6,1), (-7,2), (-1,3), (-5,4), (8,5), (-2,6), (4,7), (-9.8), (-3,9).

Just one of these proves to be minimal (-1,3)= 1^2+2*3^2 = 19.

In the above, k takes values 2, 3, 1, 3, 6, 4, 6, 11, 9. While quadratic reciprocity is not necessary here since we are given the conditions on the prime that X^2==-2 Mod p, if we were to pursue that, we have that the primes are of the form 8X+1 and 8X+3, and 2 also appears. Now looking over the k above, we find that all the odd ones are multiples of those kind of primes, which suggests to us they also have the same form, which is m^2 + 2n^2.

It is not hard to show that the product of (a^2+2b^2)(c^2+2d^2) = (ac+/-2bd)^2 + 2(ad-/+bc)^2 are of the same form. If the same thing could be worked out for division, that might be helpful, particularly if it could be shown that k was of that form. Since then it could be divided out.

I notice that the problem includes the case where k=2, or a multiple including 2. This will occur anytime the "a" term of a^2 + 2b^2 is even, and 4 appears if both are even--but this could have been reduced. Perhaps 2 is a clue as to how to proceed