Let $p$ the smallest prime divisor of $n$. (for n>1) we have that $p|3^{2n}-1$ and $p|3^{p-1}-1$. so, we will have that $p|3^{gcd(p-1,2n)}-1 = 3^{2}-1 \Longrightarrow p = 2$. $n^{2}|3^{n}+1 \Longrightarrow p^{2}|3^{n}+1 \Longrightarrow 4|3^{2k}+1$, impossible

e.lopes wrote: so, we will have that $p|3^{gcd(p-1,2n)}-1$ why?

He used the following lemma : $(a^{p}-1, a^{q}-1) = a^{(p,q)}-1$ However, $n = 1$ is a solution. Remarks : There's an easier problem in 104 NT Problems to prove that $n \not| 3^{n}+1$ for odd $n > 1$..

e.lopes wrote: Let $p$ the smallest prime divisor of $n$. (for n>1) we have that $p|3^{2n}-1$ and $p|3^{p-1}-1$. Can you explain more clearly?

$3^{n}\equiv-1\pmod{p}$ therefore $3^{2n}\equiv 1\pmod{p}$. $p|3^{p-1}-1$ by Fermat's theorem .

RDeepMath91 wrote: He used the following lemma : $ (a^{p} - 1, a^{q} - 1) = a^{(p,q)} - 1$ However, $ n = 1$ is a solution. Remarks : There's an easier problem in 104 NT Problems to prove that $ n \not| 3^{n} + 1$ for odd $ n > 1$.. Yes it is easy . If $ n|3^n+1$ then $ n$ must be even.