1
$\begingroup$

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

$\endgroup$
  • $\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$ – David C. Ullrich Jul 22 '16 at 14:53
  • $\begingroup$ Right that's more reasonable $\endgroup$ – MyNameIs Jul 22 '16 at 14:57
3
$\begingroup$

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

$\endgroup$
  • $\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$ – Bill Dubuque 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$ – Bill Dubuque 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.