Is $\frac{2^{n-1}-1}{n}$ an integer only when $n$ is an odd prime? I have the equation
$$k = \frac{2^{n-1}-1}{n}$$
and wonder if $k$ is an integer when $n$ is an odd prime. The numerator is always odd, so even $n$ have no integer solutions.
But when I run a test, it appears that only odd primes yield an integer solution.
I have no idea even how to start.
 A: No, that's not true. For example,
$$\frac{2^{340}-1}{341}$$
is an integer, but $341=11\cdot 31$. Natural numbers $n$ that satisfy the condition you've asked about are called Fermat pseudoprimes for the base $2$ (relevant Wikipedia article) and they have been studied rather extensively.
A: I think it's an integer when (1) $n$ is odd (that's obvious) and (2) $m$ divides $n-1$, where $m$ is the smallest integer $m>0$ such that $2^m \equiv 1 \pmod n$. Not fully sure though, need to refresh a bit my knowledge on this topic :) That $m$ had some special name. Such an $m$ exists for sure because $\phi(n)$ is one such $m$ (when n is odd of course) but it's not necessarily the smallest  ...   
... OK, this $m$ is called the multiplicative order of $2$ modulo $n$. So $k$ is an integer if and only if (1) $n$ is odd and (2) the multiplicative order of $2$ modulo $n$ divides the number $n-1$. In fact this statement would be true, if you take another power and not just $n-1$ in particular.
Multiplicative Order Modulo n
