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

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

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

• Why do you think so? Jan 31, 2017 at 15:35
• By computer search, $n=171$ is the smallest counterexample.
– lulu
Jan 31, 2017 at 15:40
• Quick session in Haskell reveals that's not really the truth: Prelude> filter (\x -> mod (1 + 2^x) x == 0) [1..10000] [1,3,9,27,81,171,243,513,729,1539,2187,3249,4617,6561,9747] Jan 31, 2017 at 15:40
• So this is oeis.org/A006521 Jan 31, 2017 at 15:41
• There was a Putnam problem regarding this. Jan 31, 2017 at 16:20

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

• Are you using Santiago and Lulu's comments?
– Xam
Jan 31, 2017 at 15:44
• @supersaiyan There is no general term in a closed form. We have no choice but to use a computer. Jan 31, 2017 at 15:47
• @Xam Sorry, my previous comment was incorrect about the time gap. Anyway, I didn't see their comments. This was a problem I conjectured before. And had seen it on OEIS. Jan 31, 2017 at 15:49
• Interesting paper on "primitive" solutions, thanks. Looks like there are a finite number of extra factors added in on consideration of each higher power of $3$. Jan 31, 2017 at 15:55
• @Joffan Yes. it seems to be quite difficult to find them all though. Jan 31, 2017 at 15:58

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$

• Actually, it's more general than that - if $n\mid 2^n+1$ and $p\mid 2^n+1$ then $pn\mid 2^{pn}+1$. You don't use that $p\mid n$, only that $p\mid 2^n+1$. This is where we get $n=3^2\cdot 19$, for example, since $19\mid 2^{9}+1$. Jan 31, 2017 at 19:21
• @ThomasAndrews useful insight. As I said this was a (near) transcription from the paper, so I didn't think too hard about what properties were included or restricted etc. Jan 31, 2017 at 19:31

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

• I was contemplating the same; the whole edifice comes from $1\mid 2^1{+}1$. Jan 31, 2017 at 21:49
• Okay, I've resolved the "absolutely primitive" question, and it is indeed true that the only absolutely primitive number is $1$. @Joffan Feb 1, 2017 at 21:24
• Nice work, that confirms the suspicion and legitimizes searching for "new" primes on the basis that they must arise in this progression. Feb 1, 2017 at 21:37

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