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

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.

• Program a computer. May 30, 2016 at 13:35
• @GerryMyerson Did that. None till $n \le 1000$. May 30, 2016 at 13:35
• You can use python so the scope of n can be bigger. May 30, 2016 at 13:38
• See this question. The only one is $n=1$. May 30, 2016 at 13:38
• Feb 2, 2017 at 5:16

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$.

• The footnote's incorrect. There are infinitely many of them. May 30, 2016 at 13:49
• @Dhruv Thanks, corrected. I was thinking about another old problem ... May 30, 2016 at 13:52

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.

• How can $3^n+1|3^{2n}-1$? May 30, 2016 at 13:52
• Because $3^{2n}-1=(3^n-1)(3^n+1)$. May 30, 2016 at 13:52
• Oh! There was a typo earlier. Sorry. May 30, 2016 at 13:54