# Congruence Proof

• Apr 2nd 2011, 01:08 AM
Rocky
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!

• Apr 2nd 2011, 08:37 AM
Opalg
Quote:

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 $\displaystyle a = x^{(p-1)/3}.$ Then $\displaystyle (a-1)(a^2+a+1) = a^3-1 = x^{p-1}-1\equiv0\pmod p$, and on multiplying by the inverse of $\displaystyle a-1$ you get $\displaystyle 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 $\displaystyle x^{(p-1)/3$ will not be equal to 1 mod p.
• Apr 3rd 2011, 12:36 PM
melese
Quote:

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

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

For the second part, the only thing that I was able to show is that $\displaystyle x^2+xy+y^2\equiv0\pmod p$ for some integers $\displaystyle x$ and $\displaystyle y$. Maybe it helps.
• Apr 3rd 2011, 12:53 PM
Opalg
Quote:

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?
• Apr 3rd 2011, 01:22 PM
topsquark
I have a thought, but I don't know much about quadratic residues. Perhaps someone can pick up where I leave off.
$\displaystyle p = x^2 + xy + y^2 \implies y^2 + xy + (x^2 - p) = 0$

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

-Dan
• Apr 4th 2011, 04:16 AM
Opalg
Quote:

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 $\displaystyle F(x,y) = ax^2+bxy+cy^2$ is $\displaystyle \Delta \stackrel{\mathrm{d{e}f}}= b^2-4ac$. The form is said to be reduced if $\displaystyle |b|\leqslant a\leqslant c$ and $\displaystyle b\geqslant0$ if either $\displaystyle |b|=a$ or $\displaystyle a=c.$ It is primitive if $\displaystyle \text{gcd}(a,b,c) = 1.$ The form represents the integer k if $\displaystyle F(x,y) = k$ for some integers $\displaystyle 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 $\displaystyle 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 $\displaystyle p\equiv1\pmod3$. There are three cube roots of 1 (mod p). We know that if $\displaystyle a\ne1$ is one of them then $\displaystyle a^2+a+1\equiv0\pmod p.$ This implies that $\displaystyle 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 $\displaystyle p$ because $\displaystyle F(1,0)=p$. Hence the form $\displaystyle x^2+xy+y^2$ also represents $\displaystyle p$.