Results 1 to 6 of 6

Math Help - Congruence Proof

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    5

    Congruence Proof

    Let p ≡ 1 (mod 3) be prime. Show that there exists an integer a such that a^2 + a + 1 ≡ 0 (mod p).

    Then show that p = x^2 + xy + y^2 for some integers x and y.


    In all honesty I have very little idea as to where to begin with this problem. Having completed several proofs (which appear similar) which rely on both quadratic reciprocity and the use of Minkowski's Theorem, I have attempted to use these techinques here, though to little success.

    If anybody could help to get me started then that would be very much appreciated! Many thanks!


    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Rocky View Post
    Let p ≡ 1 (mod 3) be prime. Show that there exists an integer a such that a^2 + a + 1 ≡ 0 (mod p).

    Then show that p = x^2 + xy + y^2 for some integers x and y.


    In all honesty I have very little idea as to where to begin with this problem. Having completed several proofs (which appear similar) which rely on both quadratic reciprocity and the use of Minkowski's Theorem, I have attempted to use these techinques here, though to little success.

    If anybody could help to get me started then that would be very much appreciated! Many thanks!


    For the first part, Fermat's little theorem is all you need. Take any integer x not congruent to 0 or 1 (mod p), and let a = x^{(p-1)/3}. Then (a-1)(a^2+a+1) = a^3-1 = x^{p-1}-1\equiv0\pmod p, and on multiplying by the inverse of a-1 you get a^2+a+1\equiv0\pmod p.

    Edit. Sorry, that doesn't work. Just because x is not congruent to 1 it doesn't follow that a is not congruent to 1. But maybe you can see how to fix that by choosing x more carefully?

    Second edit. I think I see how to fix it. The multiplicative group of nonzero residue classes mod p is cyclic, so you could take x to be a generator. Then x^{(p-1)/3 will not be equal to 1 mod p.
    Last edited by Opalg; April 2nd 2011 at 11:34 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by Rocky View Post
    Let p ≡ 1 (mod 3) be prime. Show that there exists an integer a such that a^2 + a + 1 ≡ 0 (mod p).

    Then show that p = x^2 + xy + y^2 for some integers x and y.


    In all honesty I have very little idea as to where to begin with this problem. Having completed several proofs (which appear similar) which rely on both quadratic reciprocity and the use of Minkowski's Theorem, I have attempted to use these techinques here, though to little success.

    If anybody could help to get me started then that would be very much appreciated! Many thanks!


    I'm going to try answer the first part; for the second part I think it's a partial answer.

    Note that (4,p)=1. Multiply both sides by 4 to get the equivalent congruence 4a^2+4a+4=(2a+1)^2+3\equiv0\pmod p, then (2a+1)^2\equiv-3\pmod p. There are solutions if and only if -3 is a quadratic residue of p . So showing that -3 is a quadratic residue of p implies that there exists a solution a . For example, let p=19 , then -3\equiv16=4^2\pmod{19}, hence 2a+1\equiv\pm4\pmod{19} giving a\equiv11, 7\pmod{19}.

    Since p\equiv1\pmod3, p is of the form 3k+1, and it's clear that k is even. So p is of the form 6m+1.
    Given that p is an odd prime, there's a theorem: -3 is a quadratic residue of p if and only if p\equiv1\mod6 . Hence the result.

    For the second part, the only thing that I was able to show is that x^2+xy+y^2\equiv0\pmod p for some integers x and y . Maybe it helps.
    Last edited by melese; April 3rd 2011 at 01:00 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Rocky View Post
    Then show that p = x^2 + xy + y^2 for some integers x and y.
    This is just an idle thought, but I wonder if you could get somewhere with this part of the problem by mimicking Lagrange's proof of Fermat's theorem about sums of two squares?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,842
    Thanks
    320
    Awards
    1
    I have a thought, but I don't know much about quadratic residues. Perhaps someone can pick up where I leave off.
    p = x^2 + xy + y^2 \implies y^2 + xy + (x^2 - p) = 0

    The discriminant -3x^2 + 4p must be equal to n^2 = 4p - 3x^2. Does quadratic residues have something to say about this one?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Opalg View Post
    This is just an idle thought, but I wonder if you could get somewhere with this part of the problem by mimicking Lagrange's proof of Fermat's theorem about sums of two squares?
    Yes, I think that idea can be made to work. It requires some knowledge (which I lack) of Gauss's theory of integral quadratic forms. There is a brief exposition of that here (link to PlanetMath page).

    The discriminant of the quadratic form F(x,y) = ax^2+bxy+cy^2 is \Delta \stackrel{\mathrm{d{e}f}}= b^2-4ac. The form is said to be reduced if |b|\leqslant a\leqslant c and b\geqslant0 if either |b|=a or a=c. It is primitive if \text{gcd}(a,b,c) = 1. The form represents the integer k if F(x,y) = k for some integers x,y. Two forms are equivalent if they represent the same set of integers. It is known that every primitive form with discriminant –3 is equivalent to the reduced form x^2+xy+y^2. Most of this is explained in the above PlanetMath link, which illustrates, but does not properly describe, the reduction process (Gauss's algorithm) for constructing equivalences.

    Now back to the problem about p\equiv1\pmod3. There are three cube roots of 1 (mod p). We know that if a\ne1 is one of them then a^2+a+1\equiv0\pmod p. This implies that F(x,y) \stackrel{\mathrm{d{e}f}}= px^2 + (2a+1)xy + \left(\frac{a^2+a+1}p\right)y^2 is a primitive form with discriminant –3. It represents  p because F(1,0)=p. Hence the form x^2+xy+y^2 also represents  p.
    Last edited by Opalg; April 4th 2011 at 05:20 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 19th 2011, 10:59 PM
  2. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 22nd 2010, 02:50 PM
  3. Congruence Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 20th 2010, 12:30 PM
  4. Proof of a congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 19th 2009, 06:08 AM
  5. Proof congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 19th 2007, 09:13 AM

Search Tags


/mathhelpforum @mathhelpforum