Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 0 down vote accepted

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.

share|improve this answer
    
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$$

share|improve this answer

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$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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