Show that $n$ does not divide $2^n - 1$ where $n$ is an integer greater than $1$? [duplicate]
Solution 1:
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.