Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

To motivate my question, recall the following well-known fact: Suppose that $p\equiv 1\pmod 4$ is a prime number. Then the equation $x^2\equiv -1\pmod p$ has a solution.

One can show this as follows: Consider the following polynomial in ${\mathbb Z}_p[x]$: $x^{4k}-1$, where $p=4k+1$. The roots of this polynomial are precisely the elements of ${\mathbb Z}_p^*$, each one with multiplicity 1. The polynomial factors as $(x^{2k}-1)((x^k)^2+1)$, and it follows that if $a$ is any element of ${\mathbb Z}_p^*$ with $a^{2k}\ne 1$ (and there are precisely $(p-1)/2$ possible such $a$), then $b=a^k$ satisfies $b^2\equiv -1\pmod p$.

Of course, there are other arguments, but I am interested in pursuing this line of reasoning. My question is the following:

From the quadratic reciprocity law, we have that $x^2\equiv -2\pmod p$ has a solution iff $p\equiv 1$ or $3\pmod 8$. Is there a proof of the right-to-left implication using some polynomial and appropriate counting of roots, as in the case shown above?

share|improve this question
1  
It seems to me that your example works because the polynomial factors over Z, and then you can deduce facts about p as corollaries. On the other hand, $x^2+2$ doesn't factor over Z, so I sort of doubt the same method will work. On the other hand, I know next to nothing about number theory -- I'd love to be proven wrong... –  Aaron Mazel-Gee Nov 10 '10 at 7:25
    
Is this argument taken from the book of Weil? –  awllower Feb 26 '11 at 8:30
1  
@awllower: Sorry for not replying sooner; didn't have the chance to check back for a while. I found the argument on my own, and then reading Cox's book mentioned in a comment below I saw the general context of it. I have now seen it in Weil's book as well; I am studying this book, very beautiful. –  Bruce George Apr 17 '11 at 16:16

3 Answers 3

up vote 14 down vote accepted

If $p=8k+1$ then consider $a$ with $a^{4k}\equiv-1$ (mod $p$). Let $b=a^k-a^{7k}$. Then $$b^2=a^{2k}-2a^{8k}+a^{14k}\equiv a^{2k}(1+a^{4k})-2 \equiv-2\pmod{p}.$$ For $p\equiv3$ (mod $8$) this argument will also work but you need to use the Galois field $GF(p^2)$ rather than the integers modulo $p$.

share|improve this answer
    
Many thanks! This answer and the one by David indicate that there is much more here than I first thought. I'll go read a little about it. –  Bruce George Nov 10 '10 at 16:21

Similar arguments work for other cases as well. For example, if $p = 1 \mod 3k$, find $a$ such that $a^{3k}=1$ and $a^k \neq 1$. Set $z=a^k$, then $z^2+z+1=0$ and we deduce that $(z - z^2)^2 = -3$.

For a larger example, if $p=5k+1$, then there is an $a$ in $\mathbb{F}_p$ with $a^{5k}=1$ and $a^k \neq 1$. Let $z=a^k$, so $z^4+z^3+z^2+z+1=0$.

Let $b = z - z^2 - z^3 + z^4$. Then $$b^2 = z^8 - 2 z^7 - z^6 + 4 z^5 - z^4 - 2 z^3 + z^2=$$ $$-z^4 - z^3 - z^2 - z + 4 = 5.$$

So $p \equiv 1 \mod 5$ implies that $\left( \frac{5}{p} \right)=1$. Just as in Robin's answer, you can also prove that $p \equiv 4 \mod 5$ implies $\left( \frac{5}{p} \right)=1$ in this manner, but it is more difficult: the element $z$ will live in $\mathbb{F}_{p^2}$, and you will need to check that $b$ lives in $\mathbb{F}_{p}$.

In fact, for every squarefree $M$, let $\Delta$ be $|M|$ if $M \equiv 1 \mod 4$ and $\Delta=4 |M|$ otherwise. Then you can prove in this manner the statement "if $p = 1 + \Delta k$ then $\left( \frac{\Delta}{p} \right) = 1$." The first steps are the same in each case: find $a$ in $\mathbb{F}_p$ such that $a^{\Delta k}=1$ but $a^{d k} \neq 1$ for any proper divisor $d$ of $\Delta$. Let $z=a^k$, so $z$ is a primitive $\Delta$ root of unity in $\mathbb{F}_p$. At this point, some magic polynomial $g_M$ is introduced, such that $g_M(z)^2 = M$. If you want to prove the full quadratic reciprocity law, you can do so using this approach as well, but you will need to work in finite fields of non-prime order.

I often thought it would be fun to assign a class the job of finding the magic polynomials $g_M$, for various values of $M$, and see if they could guess the general pattern. Hint: $g$ stands for "Gauss sum".

share|improve this answer
    
David, many thanks for your answer. Just in case, do you know of a reference where to learn about these ideas? –  Bruce George Nov 10 '10 at 16:22
2  
I learned this from Chapter 1 of Serre's Course in Arithmetic. Like all of Serre's writing, it is very clear and very concise. If anyone knows a more beginner friendly exposition, similar to the one I started here, I'd be curious to know a reference. –  David Speyer Nov 10 '10 at 16:53
    
Thank you. Do you know "Primes of the form $x^2 + ny^2$"? –  Bruce George Nov 10 '10 at 21:49
    
Yes, I do. If you can follow Cox's book, you will have no trouble with Serre. –  David Speyer Nov 11 '10 at 0:29
    
@David: Many thanks for the tip. I've been reading (and enjoying) Serre's book. –  Bruce George Dec 18 '10 at 3:15

If I remember correctly, this approach with a Gauss sum (associated to an 8th root of 1 in a finite field) is used in the first page or two of Serre's Cours d'Arithmetique to determine the "supplementary law" for $\left( \frac{2}{p} \right)$. The magical algebraic identity in this case is that if $a^4 = -1$, then $(a \pm 1/a)^2 = \pm 2$.

share|improve this answer
    
It's actually $a^2$ in the numerator (you have $0 = a^4 + 1 = (a^2 +1)^2 - 2a^2$ and similarly for the other sign). –  Geoff Robinson Aug 7 '11 at 9:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.