Clearly $2^n - 1$ is an odd integer, therefore, let $n$ be an odd integer and it divides $2^n - 1$. We can write $2^n - 1 = (2-1)(2^{n-1} + \cdots \cdots + 1) = (2^{n-1} + \cdots \cdots + 1)$

From here on I don't know how to proceed?


Suppose contrary that an integer $n>1$ exists such that $n\mid 2^n-1$. Clearly, $n$ is odd. Take $p$ to be the smallest prime dividing $n$. Then, $p\mid 2^n-1$ and $p\mid 2^{p-1}-1$. Hence, $p\mid 2^d-1$, where $d:=\gcd\big(n,p-1\big)$. However, as $p$ is the smallest prime divisor of $n$, we have $d=1$. Hence, $p\mid 2^d-1=1$, a contradiction. Hence, $n$ does not exist.

Related Question for Interested Party: There exist infinitely many $n\in\mathbb{N}$ such that $n\mid 2^n+1$. Examples are $n=3^k$, $n=3^{2+k}\cdot 19$, and $n=3^{4+k}\cdot 19\cdot 163$, where $k\in\mathbb{N}_0$. My question is as follows.

For any given $r\in\mathbb{N}$, does there exist $n\in\mathbb{N}$ with exactly $r$ prime divisors such that $n\mid 2^n+1$? (If such an $n$ exists for a particular $r$, it can be easily shown that $3^kn$ is also a solution for every $k\in\mathbb{N}_0$.)

EDIT: Problem 5 (pages 5-6) of this link answers the question above. In case this link dies again, I am referring to Problem 5 of IMO2000.

  • 3
    $\begingroup$ Sorry for making a comment on your problem 1 year ago, but why does $p | 2^d - 1$ $\endgroup$ – stenvik team Aug 23 '16 at 10:33
  • 1
    $\begingroup$ @stenvikteam It is well known that $\gcd(a^k-1,a^l-1)=a^{\gcd(k,l)}-1$ for any positive integers $k$, $l$, and $a>1$. $\endgroup$ – user593746 Oct 24 '18 at 14:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.