If $n\mid (2^n-1)$, then $n=1$.

Somehow I am unsure if I got this right, my 'proof' seems to 'easy'. Can you please give me feedback?

So I take a prime divisor $p\mid n$. Then $p\mid (2^n-1)$, hence $2^n\equiv 1\mod p.$

So $2$ has multiplicative order $n$ in $\Bbb F_p^\times$ and therefore, by Lagrange's theorem, $n\mid (p-1)$. But since we also have $p\mid n$, this is only possible for $p=1$.

  • $\begingroup$ No, $x^n=1$ in a group does not imply that the order of $x$ is $n$; it only implies that the order of $x$ divides $n$. $\endgroup$ Jul 22 '16 at 14:53
  • $\begingroup$ Right that's more reasonable $\endgroup$
    – MyNameIs
    Jul 22 '16 at 14:57
  • $\begingroup$ a duplicate $\endgroup$
    – Aven Desta
    Jan 23 at 18:44

Hint $ $ mod $\rm\color{#c00}{least}$ prime $\,p\mid n\!:\ 2^n \equiv 1\Rightarrow\, 2\,$ has order $\,k\mid n\,\color{#c00}{\Rightarrow}\ k \ge$ $\,p\,\Rightarrow\, 2^{p-1}\!\not\equiv 1\,\Rightarrow\!\Leftarrow$

The key Idea is: $ $ if $\ a\not\equiv 1,\,\ a^n\equiv 1\,$ then the order of $\,a\,$ is $\,\ge\,$ least prime $\,p\mid n.$

  • $\begingroup$ Are you a bot? That answer came so damn quick, i couldn't even type it that fast. $\endgroup$
    – MyNameIs
    Jul 22 '16 at 14:53
  • $\begingroup$ @MyNameIs It's one of my old sci.math answers, where it was a FAQ. $\endgroup$ Jul 22 '16 at 14:55
  • $\begingroup$ So from $2^n\equiv 1\mod p$ we can only conclude that $2$ has order a divisor of $n$ in $\Bbb F_p^\times$? $\endgroup$
    – MyNameIs
    Jul 22 '16 at 14:55
  • $\begingroup$ @MyNameIs That's all we need here. Every divisor $>1$ of $\,n\,$ is $\ge$ the least prime factor $\,p\,$ of $\,n\,$ (by uniqueness of prime factorizations). $\endgroup$ Jul 22 '16 at 14:58
  • $\begingroup$ Thank you. In the last step you said $k\geq p$ implies $2^{p-1}\not\equiv1$. How did you conclude that? $\endgroup$
    – MyNameIs
    Jul 22 '16 at 15:09

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.