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.
On
Proof by Contradiction. $$n|3^n+1 \implies n| (n-3)^n-1$$ Now let the smallest prime factor of $n$ be $p$. Note that by Fermat's Little Theorem $$p|(n-3)^{p-1}-1$$ We also have $$p|(n-3)^n-1$$ So we have that $$\begin{align}p|\gcd((n-3)^{p-1}-1, (n-3)^n-1) & \\ \implies (n-3)^{\gcd(p-1,n)}-1=n-4 \equiv 0 \pmod {p} \end{align}$$
This follows from here and the fact that $p$ is the smallest prime divisor.
So we have $p|4$. But $p$ is odd. Contradiction.
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.$