9
$\begingroup$

For which prime numbers $p$ is $2$ a quadratic residue modulo $p$.

I know that $2$ is a quadratic residue iff $$2^{\frac{p-1}{2}} =1 \; \bmod \;(p) $$ so $$2^{p-1} =1 \; \mod \; (p). $$ But I don't know what to do.

$\endgroup$
2
  • 2
    $\begingroup$ $2$ is a QR of the odd prime $p$ if and only if $p\equiv \pm 1\pmod{8}$. Proofs take a while. The most common one involves manipulation of factorials. $\endgroup$ May 9, 2015 at 21:38
  • $\begingroup$ See also this blog post which refers to this answer. $\endgroup$ Dec 2, 2016 at 12:20

3 Answers 3

19
$\begingroup$

Let $s = \frac{p-1}{2}$, and consider the $s$ equations

$$\begin{align} 1&= (-1)(-1) \\ 2&=2(-1)^2 \\ 3&= (-3)(-1)^3 \\ 4&= 4 (-1)^4 \\ & \quad\quad \ldots\\ s&= (\pm s)(-1)^s \end{align}$$

Where the sign is always chosen to have the correct resulting sign.

Now multiply the $s$ equations together. Clearly on the left we have $s!$. On the right, we have a $2,4,6,\dots$ and some negative odd numbers. But note that $2(s) \equiv -1 \mod p$, $2(s-1) \equiv - 3 \mod p$, and so on, so that the negative numbers are the rest of the even numbers mod $p$, but disguised. So the right side contains $s! (2^s)$ (where we intuit this to mean that one two goes to each of the terms of the factorial, to represent the even numbers $\mod p$).

We only have consideration of $(-1)^{1 + 2 + \ldots + s} = (-1)^{s(s+1)/2}$ left.

Putting this all together, we get that $2^s s! \equiv s! (-1)^{s(s+1)/2} \mod p$, or upon cancelling factorials that $2^s \equiv (-1)^{s(s+1)/2}$. And $s(s+1)/2 = (p^2 - 1)/8$, so we really have $2^{(p-1)/2} \equiv (-1)^{(p^2 - 1)/8}$.

So it depends on $p \pmod 8$. [This is probably the involved manipulation of factorial proof that André alludes to].

$\endgroup$
7
$\begingroup$

The other method is based on roots of unity $$\sqrt{2}e^{2i \pi /8}= 1+i$$ For $p$ odd $$(\sqrt{2}e^{2i \pi /8})^p = \sqrt{2} 2^{(p-1)/2}e^{2i \pi /8} (e^{2i \pi /8})^{p-1}=(1+i)\left(\frac{2}{p}\right)i^{(p-1)/2}$$

$$(1+i)^p \equiv 1^p+i^p \equiv 1+i (-1)^{(p-1)/2}\equiv (1+i) i^{(p-1)/2} (-1)^{(p^2-1)/8} \bmod p $$ Thus $$ \left(\frac{2}{p}\right) \equiv (-1)^{(p^2-1)/8} \bmod p$$

$\endgroup$
1
  • $\begingroup$ (+1) The real part of $(1+i)^p\equiv1\pmod{p}$, which is the real part of $2^{\frac{p-1}2}\sqrt2e^{\frac{\pi i}4p}\pmod{p}$. Then we only need look at the real part of $\sqrt2e^{\frac{\pi i}4p}\pmod{p}$ which is $1$ when $p\equiv\pm1\pmod8$. $\endgroup$
    – robjohn
    Nov 11, 2020 at 14:27
6
$\begingroup$

The second supplementary law of quadratic reciprocity says that: $$\biggl(\frac{2}p\biggr)=\bigl(-1\bigr)^{\tfrac{p^2-1}8}$$ Namely, $2$ is a square modulo $p$ if and only if $p\equiv\pm 1\mod 8$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .