Prime & Congruences

  • Thread starter kingwinner
  • Start date
  • #1
1,270
0
"Let p be a prime such that there exists a solution to the congruence [tex]x^2\equiv - 2\mod p[/tex].
THEN there are integers a and b such that [tex]a^2 + 2b^2 = p[/tex] or [tex]a^2 + 2b^2 = 2p[/tex]."
============================

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|(x2 -2), what's next?

Any help is appreciated!
 

Answers and Replies

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

The starting point is that, if you have [itex]a^2 + 2b^2[/itex], you may factorize this expression in [itex]\mathbb Z\left[\sqrt{-2}\right][/itex] as [itex]\left(a+\sqrt{-2}b\right)\left(a-\sqrt{-2}b\right)[/itex]; 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).
 
  • #3
CRGreathouse
Science Advisor
Homework Helper
2,824
0
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.
 
  • #4
402
1
Try reading this document:

http://math.uga.edu/~pete/4400quadrings.pdf" [Broken]
 
Last edited by a moderator:
  • #5
CRGreathouse
Science Advisor
Homework Helper
2,824
0
I don't think that's accessible for the OP.
 
  • #6
402
1
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.
 
  • #7
CRGreathouse
Science Advisor
Homework Helper
2,824
0
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.
 
  • #8
1,056
0
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
 
Last edited:

Related Threads on Prime & Congruences

Replies
9
Views
6K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
8
Views
9K
  • Last Post
Replies
4
Views
3K
Top