If $p\mid (3^n+1)$, then $p\equiv 1\pmod{3}$ 
Show that if $p> 2$ is a prime, $n > 1$ is odd and $p\mid (3^n+1)$,
  then $p\equiv 1\pmod{3}$.

Since $n$ is odd, we have $3^{n+1} \equiv -3 \pmod{p}$ is a quadratic residue. Then I thought about using Quadratic Reciprocity but didn't see how to apply it. 
We have $x^2 \equiv -3 \pmod{p}$ for some integer $x$. By Fermat's Little Theorem we have $$x^{p-1} \equiv x^2 \cdot x^{p-3} \equiv -3 \cdot x^{p-3} \equiv 1 \pmod{p}.$$ Thus, $x^{p-3} \equiv -3^{-1} \pmod{p}$. 
I didn't see how to get a contradiction if $p \equiv 2 \pmod{3}$.
 A: Lemma: for an odd prime $q,$ we always have
$$ (-3|q) = (q |3). $$
Proof: if $q \equiv 1 \pmod 4,$ then
$$ (-3|q) = (-1|q)(3|q) = (3|q) = (q|3). $$
If $q \equiv 3 \pmod 4,$ then
$$ (-3|q) = (-1|q)(3|q) = -(3|q) = (q|3). $$
In the lemma, $3$ can be replaced by any prime $r \equiv 3 \pmod 4.$ 
Let $n = 2k+1.$ We have $1 + 3^n = 1 + 3 (3^k)^2 = 1 + 3 w^2.$ If $p \equiv 2 \pmod 3$ and
$$ x^2 + 3 y^2 \equiv 0 \pmod p,  $$ assume $y$ is not divisible by $p.$
Then $y$ has a multiplicative inverse $\pmod p.$
$$ x^2 \equiv -3 y^2  \pmod p,  $$
$$ \frac{x^2}{y^2} \equiv -3 \pmod p,  $$
$$ \left( \frac{x}{y} \right)^2 \equiv -3 \pmod p. $$
This contradicts $p \equiv 2 \pmod 3,$ so actually $y$ is divisible by $p.$ It follows that $x$ is also divisible by $p.$
Back to the original problem, we have $p \equiv 2 \pmod 3$ and
$$  1 + 3 w^2 \equiv 0 \pmod p.$$
However, this implies $1$ is divisible by $p,$ which is false
====================================================================
The easy proposition is this: we are given a quadratic form 
$$ a x^2 + b x y + c y^2 $$ with discriminant
$$  \Delta = b^2 - 4 a c,$$ finally an odd prime $q$ such that
$$ (\Delta | q) = -1. $$
IF
$$ a x^2 + b x y + c y^2 \equiv 0 \pmod q $$ THEN both
$$  x,y \equiv 0 \pmod q, $$ and we get the extra
$$ a x^2 + b x y + c y^2 \equiv 0 \pmod {q^2} $$
A: This may qualify as cheating, but I will use a few known facts from Wikipedia. First of all, indeed $3^{n+1} \equiv -3 \pmod{p}$, where $n+1$ is even, thus 
$$\left(\frac{-3}{p}\right)=1 \Rightarrow \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)=1 \tag{1}$$
But
$$\left(\frac{-1}{p}\right)=\left\{\begin{matrix}
1, & p \equiv 1 \pmod{4} \\ 
-1,& p \equiv 3 \pmod{4}  
\end{matrix}\right. \color{red}{\text{ and }} \left(\frac{3}{p}\right)=\left\{\begin{matrix}
1, & p \equiv 1 \text{ or } 11 \pmod{12} \\ 
-1, & p \equiv 5 \text{ or } 7 \pmod{12} 
\end{matrix}\right.$$
Due to $(1)$, we have 
$$\left\{\begin{matrix}
\left(\frac{-1}{p}\right)=1\\ 
\left(\frac{3}{p}\right)=1 
\end{matrix}\right. \color{red}{\text{ or }} \left\{\begin{matrix}
\left(\frac{-1}{p}\right)=-1\\ 
\left(\frac{3}{p}\right)=-1 
\end{matrix}\right. $$
Or, for the first case
$$\left\{\begin{matrix}
\left(\frac{-1}{p}\right)=1\\ 
\left(\frac{3}{p}\right)=1 
\end{matrix}\right. \Leftrightarrow \left\{\begin{matrix}
p \equiv 1 \pmod{4}\\ 
p \equiv 1 \text{ or } 11 \pmod{12} 
\end{matrix}\right. \Rightarrow p \equiv 1 \pmod{12}$$
and for the latter 
$$\left\{\begin{matrix}
\left(\frac{-1}{p}\right)=-1\\ 
\left(\frac{3}{p}\right)=-1 
\end{matrix}\right. \Leftrightarrow \left\{\begin{matrix}
p \equiv 3 \pmod{4}\\ 
p \equiv 5 \text{ or } 7 \pmod{12} 
\end{matrix}\right. \Rightarrow p \equiv 7 \pmod{12}$$
As a result 
$$p \equiv 1 \pmod{12} \color{red}{\text{ or }} p \equiv 7 \pmod{12} \Rightarrow \\ p \equiv 1 \pmod{3} \color{red}{\text{ or }} p \equiv 7 \pmod{3} \Rightarrow \\ p \equiv 1 \pmod{3}$$
A: You have shown that $(\frac{-3}{p}) = 1$ in this case. The truth is, in fact, that $(\frac{-3}{p}) = 1 \iff p \equiv 1 \pmod{3}$, which is what you are trying to prove.
$(\frac{-3}{p}) = (\frac{-1}{p})(\frac{3}{p})$ due to multiplicity of Legendre symbol. 
From Euler's criterion, $(\frac{-1}{p}) = (-1)^{\frac{p-1}{2}}$.
From QR, $(\frac{3}{p}) = (-1)^{\frac{p-1}{2}}(\frac{p}{3})$.
Hence $(\frac{-3}{p}) = (-1)^{p-1}(\frac{p}{3}) = (\frac{p}{3}) = 1 \iff p \equiv 1 \pmod{3}$.
