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

• what's an "odd prime"? – Chinny84 Jul 17 '15 at 22:50
• Primes except $2$... – johannesvalks Jul 17 '15 at 22:50
• @Chinny84: A prime number that isn't $2$. – Race Bannon Jul 17 '15 at 22:50
• I know that @RaceBannon but I just thought all primes except $2$ would of been better. But that's me. – Chinny84 Jul 17 '15 at 22:53
• – Spenser Jul 17 '15 at 23:14

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