Congruence Proof

**Rocky** · April 2nd 2011, 01:08 AM

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!

**Opalg** · April 2nd 2011, 08:37 AM

Originally Posted by Rocky

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.

**melese** · April 3rd 2011, 12:36 PM

Originally Posted by Rocky

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.

**Opalg** · April 3rd 2011, 12:53 PM

Originally Posted by Rocky

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?

**topsquark** · April 3rd 2011, 01:22 PM

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

**Opalg** · April 4th 2011, 04:16 AM

Originally Posted by Opalg

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$ .

Thread: Congruence Proof

LinkBack

Thread Tools

Display