Dividing the Exponent

It is clear that it holds for $n=1$ . We will now show that it holds for no larger value of n : We will assume that there is some odd number n > 1 where $n \mid 3^n + 1$ . Let p be the smallest prime which divides n . We know that p is odd. We also know therefore that $p \mid 3^n + 1$ , ie. $3^n \equiv -1 \pmod{p}$ . Squaring both sides of this congruence gives us $3^{2n} \equiv 1 \pmod{p}$ . Now, let $ord_{p}(3)=x$ . This means that $x$ is the smallest positive integer such that $3^x \equiv 1 \pmod{p}$ (you can read more here http://en.wikipedia.org/wiki/Multiplicative_order). Evidently 3 does not divide p . Therefore $3^{\phi(p)} = 3^{p-1} \equiv 1 \pmod{p}$ . From all of this we see that $x \mid 2n$ and $x \mid p-1$ (this is a property of the multiplicative order). But we know that $gcd(n,p-1)=1$ since $p \mid n$ . So either $x=1$ or $x = 2$ . If $x=1$ then $3^{1} \equiv 1 \pmod{p}$ meaning that $p=2$ , a contradiction. Similarly, if $x=2$ then $3^{2} \equiv 1 \pmod{p}$ meaning that $p=2$ , again a contradiction. Therefore we have made a mistake with our assumption and thus the only value of n (and therefore the sum of all values) is $\fbox{1}$

same solution :)