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

  • $\begingroup$ 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? $\endgroup$ – mbjoe Mar 13 at 22:36
  • $\begingroup$ No, because of $$2^{m\cdot 2^{k+1}}=(2^{m\cdot 2^k})^2\equiv (-1)^2=1\mod p$$ $\endgroup$ – Peter Mar 13 at 22:38
  • $\begingroup$ But I just notice that your argument is also valid. $\endgroup$ – Peter Mar 13 at 22:41

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.