# In a field of prime order $p\equiv 3 \mod{4}$, why must $3$ or $-3$ be a square?

I am trying to somehow show that in $F= \Bbb{F}_p$ where $p\equiv 3\mod{4}$, we have $b^2 = 3\mod{p}$ or $b^2 = -3\mod{p}$ for some $b\in F$. I really have no idea how to approach this as I have very little number theory background. Any suggestions as to how I could approach this would be incredibly appreciated.

For context, I am trying to solve an abstract algebra homework problem and the solution rests on this statement being true.

• the product of nonresidues is a residue. They are saying $-1$ is a nonresidue – Will Jagy Dec 9 '17 at 1:32
• I'm sorry, but I'm not familiar with this terminology. – luthien Dec 9 '17 at 1:33
• en.wikipedia.org/wiki/Quadratic_residue#Prime_modulus – Will Jagy Dec 9 '17 at 1:37
• The squares $\pmod p$ are a subgroup, of index two, in the multiplicative group of nonzero elements $\pmod p.$ The square are called quadratic residues, the other coset quadratic nonresiidues. When $p \equiv 3 \pmod 4,$ we know that $-1$ is a nonresidue. – Will Jagy Dec 9 '17 at 1:42
• Ok if I just take as fact that $-1$ is a nonresidue, then if $3$ is a quadratic non-residue, it follows that $(-1)(3) = -3$ must be a quadratic residue because it is the product of two quadratic non-residues? And a similar thing is true if $-3$ is a quadratic non-residue? – luthien Dec 9 '17 at 1:46

An element $a$ in $\mathbb{F}_p^\times$ is a square if and only if, given a generator $g \in \mathbb{F}_p^\times$, we have $a = g^k$ where $k$ is even. It should be not very hard to prove on your own. Immediately we see that if $p > 2$ is odd, $a \neq 0, b \neq 0$ is not squares, then $ab$ is a square since the power of $g$ is even.

Now $-1$ is not a square if $p \equiv 3 \pmod 4$. Why? $\mathbb{F}_p^\times$ has $p-1 \equiv 2 \pmod 4$ elements, and $-1$ has order two so we must have $-1 = g^{(p-1)/2}$, and $(p-1)/2$ is odd.

Finally, to finish the proof: if $3$ is a square we're done. Otherwise, both $3$ and $-1$ are both not squares, so $-3$ is a square.

Notation: For any $k\in \Bbb N$ let $[[k]]=\{1,...,k\}=\{n\in \Bbb N:n\leq k\}.$

Let $S$ be the set of members of $[[p-1]]$ that are quadratic residues modulo $p.$

For any odd prime $p,$ the function $f:[[p-1]]\to S,$ where $f(x)\equiv x^2 \pmod p ,$ is exactly $2$-to-$1,$ because $f(x)=f(y)\iff p|(x-y)(x+y)\iff (y=x\lor y=p-x\ne x).$ So $S$ has $(p-1)/2$ members.

Now $[[p-1]]=\bigcup_{x=1}^{x=(p-1)/2} \{x,p-x\}.$

If $x\in [[(p-1)/2]]$ and neither $x$ nor $p-x$ belongs to $S,$ then there exists $y\in [[(p-1)/2]]$ such that both $y$ and $p-y$ belong to $S.$ Otherwise $S$ would have at most one member in $\{y,p-y\}$ whenever $x\ne y \in [[(p-1)/2]]$ and $S$ would have no members in $\{x,p-x\},$ implying that $S$ has at most $\;-1+(p-1)/2$ members.

But if $y\in [[(p-1)/2]]$ and $\{y,p-y\}\subset S$ then there exist $m,n\in [[p-1]]$ with $m^2+n^2\equiv y+(p-y)\equiv 0 \pmod p.$ This is not possible for prime $p\equiv -1\pmod 4.$

• BTW . Here is an unrelated very elementary problem: With the notation of my answer, prove that if $p$ is prime and $p\geq 11$ then $\forall x\in [[p-1]]\;\exists u,v\in S\;(u\ne v\land u+v\equiv x \pmod p).$ – DanielWainfleet Dec 9 '17 at 8:48