Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prime & Congruences

  1. Feb 22, 2010 #1
    "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!
  2. jcsd
  3. Feb 22, 2010 #2
    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).
  4. Feb 22, 2010 #3


    User Avatar
    Science Advisor
    Homework Helper

    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.
  5. Feb 24, 2010 #4
    Try reading this document:

    http://math.uga.edu/~pete/4400quadrings.pdf" [Broken]
    Last edited by a moderator: May 4, 2017
  6. Feb 24, 2010 #5


    User Avatar
    Science Advisor
    Homework Helper

    I don't think that's accessible for the OP.
  7. Feb 24, 2010 #6
    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.
  8. Feb 24, 2010 #7


    User Avatar
    Science Advisor
    Homework Helper

    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.
  9. Feb 24, 2010 #8
    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: Feb 25, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook