15
$\begingroup$

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?

  • 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...2010-11-10
  • 0
    Is this argument taken from the book of Weil?2011-02-26
  • 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.2011-04-17

3 Answers 3

16

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

  • 0
    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.2010-11-10
12

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

  • 0
    David, many thanks for your answer. Just in case, do you know of a reference where to learn about these ideas?2010-11-10
  • 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.2010-11-10
  • 0
    Thank you. Do you know "Primes of the form $x^2 + ny^2$"?2010-11-10
  • 0
    Yes, I do. If you can follow Cox's book, you will have no trouble with Serre.2010-11-11
  • 0
    @David: Many thanks for the tip. I've been reading (and enjoying) Serre's book.2010-12-18
  • 0
    To @ Bruce: is the problem of primes of the form $x^{2}+ny^{2}$ involved with the class field theory? Thanks in any case.2011-02-26
6

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

  • 0
    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).2011-08-07