number theory - Let $n>1$ be an odd integer . Show that $nnmid 3^n+1$

Problem from Burton's Number Theory:

Let $n>1$ be an odd integer . Show that $n\nmid 3^n+1.$

Trying by induction on $n$. The result holds for $n=3$ since $3\nmid 3^3+1=28$.

Let the result hold for $n=m\implies m \nmid 3^m+1.$

Assume contrary, let $m+1\mid 3^{m+1}+1\implies 3^{m+1}+1=k(m+1)\implies 3.3^m=km+(k-1)$.

I am unable to proceed further.Please help.

Answer

Let $\,\color{#0a0}{p= \rm least}$ prime factor of $n.\,$ ${\rm mod}\ p\!:\ 3^{\large n}\!\equiv -1\,\Rightarrow\,3^{\large 2n}\!\equiv 1\equiv 3^{\large p-1}$ so the order $\,k\,$ of $3$ satisfies $\,k\mid 2n,p\!-\!1$ so $\,\color{#c00}k\mid(2n,p\!-\!1)=(2,p\!-\!1)=\color{#c00}2\,$ by $\,n\,$ is coprime to $p\!-\!1\,$ (by $\,n\,$ has no prime $\color{#0a0}{{\rm factors}\ < p}).\,$ Thus $\,3^{\large\color{#c00}2}\!\equiv 1\pmod{\!p}\,$ so $\,p\mid 3^{\large 2}\!-1=8,\,$ contra $\,p\,$ odd, by $\,p\mid n$ odd.

Remark $\ $ The proof in S.C.B's answer is closely related. We can eliminate the $2$ in $2n$ as follows. Note $\, 1 \equiv -3^{\large n}\!\equiv (-3)^{\large n}\!\equiv (-3)^{\large p-1}$ so $\,-3\,$ has order $\,\color{#c00}{k\!=\!1},\,$ by $\,k\,$ divides the coprimes $\,n,\,p\!-\!1.\,$ Thus $\,(-3)^{\large\color{#c00}{\bf 1}}\!\equiv 1\,\Rightarrow\, 4\equiv 0\,\Rightarrow\,p\mid 4,\,$ contra $\,p\,$ odd.

Finally replace $\,-3\,$ by a positive rep $\,n\!-\!3\equiv -3\pmod{\!p}\,$ then replace the above logic on orders mod $\,p\,$ by equivalent gcd logic in the integers using $\,\gcd(a^{\large J}\!-1,a^{\large K}\!-1) = a^{\large\gcd(J,K)}\!-1.$