Find all $n$ such that $n \mid 3^n + 1$.

Question

Find all $n$ such that $n \mid 3^n + 1$.

I know we want to show that $3^n \equiv -1$ (mod $n$). I have tried using the fact that $3^{\phi(n)} \equiv 1$ (mod $n$), but I am not sure how to proceed.

Answer 1

$n$ divides $3^n + 1$ if and only if $3^n \mod n$ yields $-1$ or equivalently $n-1$ as residue

$$n | (3^n + 1) \iff 3^n \equiv -1 \equiv n-1 \pmod n$$

Then the divisibility is proved as following: $$3^n + 1 \equiv n-1 + 1 \equiv -1 + 1 \equiv 0 \pmod n$$

Note that the following method doesn't generate the whole sequence as seen in OEIS, but let $n=2\cdot5^m$ then:

$$3^{2\cdot 5^{m-1}} \equiv -1 \pmod{n}$$

The exponent of $3$ is obtained by evaluating factors of $n \mod \varphi(n)$:

$$5^m \equiv 5^{m-1} \pmod{\varphi(n)}$$

Some examples are: $\{10,50,250,1250,6250,31250,...\}$