# Understanding the proof that if $n\mid 2^n+2$ and $n>1$, then $n$ is even

While reading this question regarding OEIS sequence A006517 listing integers $$n$$ with $$n\mid 2^n+2$$, I tried to understand the proof that if $$n\mid 2^n+2$$ and $$n>1$$, then $$n$$ is even. This proof in the COMMENTS section of A006517 is:

If an odd term $$n>1$$ exists then $$n = m2^k + 1$$ for some $$k\ge1$$ and odd $$m$$. Then $$n$$ divides $$2^{m2^k} + 1$$ and so does every prime factor $$p$$ of $$n$$, implying that $$2^{k+1}$$ divides the multiplicative order of $$2$$ modulo $$p$$ and thus $$p-1$$. Therefore $$n = m2^k + 1$$ is the product of prime factors of the form $$t2^{k+1} + 1$$, implying that $$n-1$$ is divisible by $$2^{k+1}$$, a contradiction.

What I don't understand is the part in bold character.

The order mentioned in the bold part is obviously a divisor of $$m\cdot 2^{k+1}$$. Suppose, the order is even a divisor of $$m\cdot 2^k$$. Then, we have $$2^{m2^k}\equiv 1\mod p$$ which is a contradiction to $$2^{m2^k}\equiv -1\mod p$$ since $$p$$ must be odd. Hence, the order divides $$m\cdot 2^{k+1}$$ , but not $$m\cdot 2^k$$. This is only possible, if the order is a multiple of $$2^{k+1}$$
• Thank you, I think I understand now. The order is a divisor of $m \cdot 2^{k+1}$ because $(2^{m2^k}+1)(2^{m2^k}-1)=2^{m2^{k+1}}-1$ right? – mbjoe Mar 13 at 22:36
• No, because of $$2^{m\cdot 2^{k+1}}=(2^{m\cdot 2^k})^2\equiv (-1)^2=1\mod p$$ – Peter Mar 13 at 22:38