When does $n$ divide $2^n+1$?

Question

For which $n$ does $n\mid2^n+1$ ?

My hypothesis is that the only solution is $n=3^k$, for some positive integer $k$.

Answer 1

Unfortunately, your claim is false.

You can find a list where $2^n+1 \equiv 0 \pmod {n}$ here.

The smallest counterexample is $n =171$ as can be seen on the sequence.

There are some more comments here.

Interestingly, the sequence is closed under multiplication, so if $x,y$ are part of the sequence then $xy$ is as well, as is proven in the paper.

Since $3$ is part of the sequence, it follows that every number of the form $3^n$ is going to be on the sequence. So, it is true that $$2^{3^{n}} +1\equiv 0 \pmod {3^n}$$

Furthermore, we can prove that every member of the sequence is a multiple of $3$.

Answer 2

For interest and accessibility, I'll reproduce a result from the paper cited by SCB above:

Proposition: If $p \mid n$ and $n \mid 2^n{+}1$ then $pn \mid 2^{pn} {+} 1$.

Proof: Clearly $p > 2$. Set $M = 2^n$, giving $2^{pn} + 1 = (M + 1)(M^{p−1} − M^{p−2} + ... − M + 1)$.

Now $n \mid M{+}1$ and thus $M \equiv -1 \bmod p$ so
$\begin{align}M^{p−1} − M^{p−2} + ... − M + 1 &\equiv (−1)^{p−1} − (−1)^{p−2} + ... − (−1) + 1 = p \\ & \equiv 0 \bmod p \end{align}$
so that $pn \mid 2^{pn} {+} 1$

Since $3 \mid 2^3{+}1$, this also immediately gives $3^{k} \mid 2^{3^k}{+}1$.

Also (for example) given that $171 \mid 2^{171}{+}1$ and $3^2\cdot 19 = 171$, we will have $c\mid 2^c{+}1$ for any $c=3^a\cdot 19^b$ with $a\ge2$

---

Thomas Andrews points out that we only need to have $p \mid 2^n{+}1$ (rather than $p\mid n$) for the above result. This allows us directly into some non-powers-of-$3_\mathstrut$ solutions: for example, because $(n,p)=(9,19)$ with $9 \mid 2^9{+}1$ and $19\mid 2^9{+}1$, the result follows that $9\cdot 19 = 171 \mid 2^{171}{+}1$

Answer 3

More generally:

If $n\mid 2^{n}+1$ and $d\mid 2^n+1$ then $nd\mid 2^{nd}+1$.

This is because $n$ and $d$ are odd, so if $2^{n}\equiv -1\pmod d$ then $(-2)^n\equiv 1\pmod d$ and $$\begin{align}\frac{2^{nd}+1}{2^n+1}&=\frac{1-((-2)^n)^d}{1-(-2)^n} \\ &= 1+(-2)^n+(-2)^{2n}-\cdots +(-2)^{n(d-1)}\\ &\equiv 1+1+1+\cdots 1 \\&= d\equiv 0\pmod{d}.\end{align}$$

So $(2^n+1)d\mid 2^{nd}+1$ and hence $nd\mid 2^{nd}+1$.

So we can say a solution $n$ is absolutely primitive if, for each prime $p\mid n$, $2^{n/p}+1$ is not divisible by $\mathrm{lcm}(n/p,p).$

For example, $171=3^2\cdot 19$ is not absolutely primitive because $\mathrm{lcm}(171/19,19)=171\mid 2^{171/19}+1$. And $3$ is not primitive since $\mathrm{lcm}(3/3,3)=3\mid 2^{3/3}+1$.

Indeed, I wonder if there are any absolutely primitive $n$ other than $1$.

If prime $p\mid n$ and $p\mid 2^n+1$ then $2^{n}=( 2^{n/p})^p\equiv 2^{n/p}\pmod p$ and hence if $n$ is absolutely primitive, then $\frac{n}{p}$ can't be a divisor of $2^{n/p}+1$ for any prime divisor $p$ of $n$.

Now given two distinct prime factors $p,q$ of $n$, if $q^k\mid 2^n+1$ and $q^k\not \mid 2^{n/p}+1$ then we must have $q\mid \sum_{i=0}^{p-1} (-2)^{ni/p}$. But if $q\mid 2^{n/p}+1$, we'd have $(-2)^{n/p}\equiv 1\pmod{q}$ and thus $q\mid p$, which is not possible.

This means that, if $n$ is absolutely primitive, then for each prime $p\mid n$ there must be another prime $q\mid n$ such that $q\not\mid 2^{n/p}+1$ and $q\mid 2^{n}+1$.

But if $2^{n/p}+1$ is not divisible by $q$ and $2^{n}+1$ is divisible by $p$, then $-1$ must be a non-trivial $p$th power, modulo $q$, and thus $q-1$ must be divisible by $p$.

So if $p$ is the largest prime factor of $n$, we get that no such $q$ can exist.

Therefore, for any $n$ with $n\mid 2^n+1$ either $n=1$ or the largest prime $p\mid n$ satisfies $\frac{n}{p}\mid 2^{n/p}+1$ and $p\mid 2^{n/p}+1$.

Answer 4

It is not necessary that $n = 3^k$, but it is sufficient.

Using the Lifting the Exponent Lemma, if $p$ is a prime and $a$ and $b$ are natural numbers not divisible by $p$, assuming $p|a+b$, then $$v_p(a^n+b^n)=v_p(a+b) + v_p(n).$$

Now putting $p=3$, $a=1$ and $b=2$, we get $$3^{n+1} | 2^{3^n}+1.$$