Find all odd integers $n \geq 1$ such that $n$ divides $3^{n}+1$.


Let $n>1$ such that $n$ divides $3^{n}+1$. Let $p$ be the smallest prime factor of $n$, which is therefore odd, and satisfies $p>3$. Then $3^{2 n} \equiv 1 \pmod{p}$. Let $\omega$ be the order of 3 modulo $p$. Then $\omega$ divides $2 n$. On the other hand, by Fermat's Little Theorem, $3^{p-1} \equiv 1 \pmod{p}$. Thus $\omega$ divides $p-1$. We deduce that $\omega$ divides $\gcd(2 n, p-1)$. Given the condition on $p$, we necessarily have $\omega=1$ or 2. In the first case, $3 \equiv 1 \pmod{p}$ and thus $p=2$, which is excluded. In the second case, $3^{2} \equiv 1 \pmod{p}$ and thus $p$ divides 8, which is also excluded. We conclude that $n=1$.