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.

  • 4
    $\begingroup$ the product of nonresidues is a residue. They are saying $-1$ is a nonresidue $\endgroup$ – Will Jagy Dec 9 '17 at 1:32
  • $\begingroup$ I'm sorry, but I'm not familiar with this terminology. $\endgroup$ – luthien Dec 9 '17 at 1:33
  • $\begingroup$ en.wikipedia.org/wiki/Quadratic_residue#Prime_modulus $\endgroup$ – Will Jagy Dec 9 '17 at 1:37
  • $\begingroup$ 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. $\endgroup$ – Will Jagy Dec 9 '17 at 1:42
  • $\begingroup$ 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? $\endgroup$ – 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.$

  • $\begingroup$ 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).$ $\endgroup$ – DanielWainfleet Dec 9 '17 at 8:48

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.