# Showing that $3^{(p+1)/4}$ satisfies $x^2 \equiv 3 \mod p$ for primes $p\equiv11 \mod 12$

Let $p$ a prime with $p\equiv11 \mod 12$.
I have to prove that $3^{(p+1)/4}$ is a solution to $x^2\equiv3\mod p$.

This is how I start:
There is a solution because $p\equiv11 \mod 12 \Rightarrow \left(\frac{3}{p}\right)=1$.
$p\equiv11 \mod 12 \Rightarrow p=12k+11 \Rightarrow (3^{(p+1)/4})^2 = 3^{6(k+1)}$.

I got stuck here and don't have any idea how to continue. Thanks

-

First note that $(p+1)/4$ is an integer. You now need to show that the proposed $x$ "works."

So you need to show that $3^{(p+1)/2}\equiv 3\pmod{p}$. This is equivalent to showing that $3^{(p-1)/2}\equiv 1\pmod{p}$.

But that is true, since $3$ is a quadratic residue of $p$, as shown by your Legendre symbol calculation.

Remark: We can rewrite the argument in more conventional style as follows. First assert that since $3$ is a QR, we have $3^{(p-1)/2}\equiv 1\pmod{p}$. Then multiply both sides by $3$, and note that $3^{(p-1)/2}\cdot 3=3^{(p+1)/2}$. But that version disguises a little the reasoning that led to it.

-
Can you explain why to show 3(p+1)/2≡3(modp) s is equivalent to showing that 3(p−1)/2≡1(modp). –  user1932595 Mar 28 '13 at 18:13
Divide both sides by $3$, and note that $\frac{p+1}{2}-1=\frac{p-1}{2}$. Or you could write the argument another way, by first asserting that $3^{(p-1)/2}\equiv 1\pmod{p}$, and then multiplying both sides by $3$. –  André Nicolas Mar 28 '13 at 18:16

If $p=12k+11\implies \frac{p-1}2=\frac{12k+11-1}2=6k+5$ which is odd

using Quadratic Reciprocity Theorem, $$\left(\frac3p\right)\left(\frac p3\right)=(-1)^\frac{(p-1)(3-1)}4=-1$$

Again, $$\left(\frac p3\right)=\left(\frac {12k+11}3\right)=\left(\frac {-1}3\right)=-1$$ as any integer $a\equiv0,\pm1\pmod 3\implies a^2\equiv0,1\pmod 3$

$$\implies \left(\frac3p\right)=1$$

$$\implies 3^\frac{p-1}2\equiv1\pmod p$$

$$\implies \left(3^\frac{p+1}4\right)^2\equiv3\pmod p$$

-

Hint $\$ If $\rm\:P = 11\!+\!12K\:$ then $\rm\:\color{#C00}{(P\!+\!1)/4 = 3\!+\!3K},\:$ therefore, by Euler's Criterion $$\rm\:(3\mid P)=1\:\Rightarrow\:mod\ P\!:\,\ 1 \equiv 3^{(P-1)/2}\Rightarrow\: 3 \equiv 3^{(P+1)/2}\! \equiv (3^{\color{#C00}{(P+1)/4}})^2 \equiv (3^{\color{#C00}{3+3K}})^2$$

-