5
$\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
    $\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$ – André Nicolas May 9 '15 at 21:38
  • $\begingroup$ See also this blog post which refers to this answer. $\endgroup$ – Martin Sleziak Dec 2 '16 at 12:20
11
$\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].

| cite | improve this answer | |
$\endgroup$
4
$\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$.

| cite | improve this answer | |
$\endgroup$
1
$\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)(\frac{2}{p})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 $$ (\frac{2}{p}) \equiv (-1)^{(p^2-1)/8} \bmod p$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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