Find all odd $n \in \mathbb{Z}^+$ such that $n\mid 3^n+1$.

Question

Find all odd $n \in \mathbb{Z}^+$ such that $n\mid 3^n+1$.

I believe that there doesn't exist any such $n$ except $1$. It is clear that $n$ can't be a multiple of $3$. Also, $3^n \equiv -1 \pmod n$. I am not able to proceed further. Could you give some hints on how to do so?

Thanks.

Answer 1

There is no such $n$, except $1$.

Proof: Let $n$ be an odd number, bigger than $1$, such that $n$ divides $3^n + 1$. Then $n$ is prime to $3$.

Let $p$ be the smallest prime divisor of $n$, and let $m$ be the order of $3$ modulo $p$, i.e. $m$ is the smallest positive integer such that $3^m \equiv 1 \mod p$. It is clear that $m \mid p - 1$, hence $m$ is prime to $n$.

Since $3^{2n} \equiv 1 \mod p$, we have $m \mid 2n$, which leads to $m \mid 2$. From here a contradiction is obvious.

---

I believe that this problem is inspired by an older one: there is no positive integer $n > 1$ such that $n \mid 2^n - 1$.

Answer 2

Suppose that $p\ge 5$ is the smallest prime divisor of $n$. It follows that $\gcd(p-1, n)=1$ and $p|n|3^n+1|3^{2n}-1$. On the other hand using Fermat's little theorem one gets $p|3^{p-1}-1$, therefore$$p|\gcd(3^{p-1}-1, 3^{2n}-1)=3^{\gcd(p-1, 2n)}-1=2 ,8$$Contradiction.