0
$\begingroup$

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

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

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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