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?



2 Answers 2


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

  • $\begingroup$ The footnote's incorrect. There are infinitely many of them. $\endgroup$ May 30, 2016 at 13:49
  • $\begingroup$ @Dhruv Thanks, corrected. I was thinking about another old problem ... $\endgroup$
    – WhatsUp
    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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.