<s>[INST] 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}$.
 [/INST] 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}$.
</s>