$3^n\equiv -1 \mod n\implies \frac{ord(3)}{2}|n\implies 3^\frac{ord(3)}{2}\equiv -1\mod \frac{ord(3)}{2}$ So $n\longleftrightarrow \frac{ord_n(3)}{2}$ and it is clear that $\frac{ord_n(3)}{2}\le n$ and so repeating the same process we reach $m=\frac{ord_m(3)}{2}$ which implies $2m|\phi(m)\le m$ a contradiction

To the contrary, assume $n\mid 3^n+1$. (Case $n=3$ is readily verified to be false so assume $n>3$ )Thus, $\pmod{n}$ we have $$3^n= -1\implies 3^2n= 1$$Since $n$ is odd and is greater than $3$, $\text{gcd}(3,n)=1$. So, $\varphi(n)\mid 2n$. If $n=\prod_i {p_i}^{a_i}$ then this implies $\frac12 \prod_i (p_i -1)\mid \prod_i p_i$, which is impossible.

Let $P$ be the smallest prime divisor of $n$ $P|3^{2n}-1$ and $P|3^{p-1}-1$ $\Rightarrow P|3^{(2n,p-1)}-1=8$.....a contradiction!