# let p be a prime number , and n a positive integer number How many values of $n$ are there such that $2^n-n$ is divisible by $p$ ??

let p be a prime number , and n a positive integer number ; How many values of n are there such that $$2^n-n$$ is divisible by p ?? thank you for helping me

• Since $p$ is prime, you'd need $2^n-n$ to be $1$ or $p$, yes? – lulu Mar 28 '17 at 12:06
• @Peter yes i mean that ; i made a mistake – user373141 Mar 28 '17 at 12:09
• @Dietrich Burde I am so sorry ; it is done – user373141 Mar 28 '17 at 12:41

There are infinitely many solutions.

To see that, note that $2^{k(p-1)}\equiv 1 \pmod p$ for all integers $k$ so we just need to find infinitely many $k$ for which $k(p-1)\equiv 1\pmod p$, but that's the same as solving $k\equiv -1\pmod p$ which clearly has infinitely many solutions.

Example: $p=17$ then take $k=16$ so we see that $2^{256}\equiv 256\pmod {17}$ and so on.

Note: this does not get all the solutions, for example with $p=17$ the smallest solution is $n=30$. Still it is enough to show that there are infinitely many.

Since $2^n-n>1$ for $n>1$, $2^n-n\mid p$ implies that $2^n-n=p$. So we have equality. For $p=2$ we have $n=2$, for $p=3$ there is no $n$, for $p=5$ we have $n=3$. In general, there are a only a few solutions, since $n$ is at most of size $\log_2(p)$.

Edit: The question was changed - I am sorry. The answer is, I think, for infinitely many $n$. The idea is related to this MO question. Actually, it is enough to show that there are infinitely many $k$ such that $k(p-1)\equiv 1 \bmod p$, see the other answer.

If we write $n=p(p-1)m+r$ with $0\le r\lt p(p-1)$, then note that (for odd $p$)

$$2^n-n\equiv2^r-r\mod p$$

hence the (asymptotic) density of $n$'s for which $2^n-n\equiv0$ mod $p$ is a fraction with denominator $p(p-1)$. For $r=(p-1)^2$ we clearly have $2^r-r\equiv0$ mod $p$, so the density is at least $1\over p(p-1)$.

For $p=2$, of course, we have $2^n-n\equiv0$ mod $2$ for all positive even numbers $n$.