Find all odd integers $n>0$ such that $n \mid 3^{n}+1$.
First, $n=1$ is a solution. Now, consider the case $n \geqslant 2$: $n$ therefore has at least one prime divisor, let $p$ be the smallest of them. We have

$$
3^{n} \equiv-1 \quad(\bmod p)
$$

We know how to manipulate the order and Fermat's theorem, and we have just seen in exercise 7 that these manipulations can solve exercises of this type. The only problem is having a -1 instead of a 1. The trick is to square our equality to make the 1 appear! Thus,

$$
\begin{gathered}
\left(3^{n}\right)^{2} \equiv(-1)^{2} \quad(\bmod p) \\
3^{2 n} \equiv 1 \quad(\bmod p)
\end{gathered}
$$

Now, let $\omega$ be the order of 3 modulo $p$. We have

$$
1 \leqslant \omega<p
$$

Then, $3^{2 n} \equiv 1(\bmod p)$ gives

$$
\omega \mid 2 n
$$

Finally, $3^{n} \equiv-1 \not \equiv 1(\bmod p)$. Indeed, otherwise we would have $p=2$ but $n$ is odd. Thus,

$$
\omega \nmid n
$$

Then, $\omega \mid 2 n$ implies that if there exists a prime number $q$ other than 2 dividing $\omega$, we would have $q|\omega| 2 n$

$$
q \mid 2 n
$$

But $\operatorname{pgcd}(q, 2)=1$ so by Gauss's lemma, $q \mid n$. Therefore, $q$ is a prime divisor of $n$ strictly less than $p$ ( $q$ divides $\omega$ so it is less than $\omega$, which is itself strictly less than $p$), which is absurd!

Thus, it follows that $\omega$ is a power of two. On the other hand, $n$ is odd, so the largest power of 2 dividing $2 n$ is 1: thus,

$$
\omega=2^{1}=2 \text { or } \omega=2^{0}=1
$$

$\omega=1$ does not work since $1 \mid n$ but $\omega \nmid n$.

Thus, $\omega=2$.

Therefore,

$$
\begin{aligned}
3^{2} & \equiv 1 \quad(\bmod p) \\
8 & \equiv 0 \quad(\bmod p)
\end{aligned}
$$

Hence $p=2$, but $n$ is odd: absurd. In conclusion, the only solution is $n=1$.