Prove that for every prime $p$ exists infinitely many integers $n$ such that $p \mid 2^n-n$.

I have no idea how to prove that.

  • 2
    $\begingroup$ If you can find one solution you can find an infinite number, since $2^{n + p \cdot (p-1)} \equiv n + p \cdot (p-1) \pmod p$. $\endgroup$ – Dan Brumleve Jan 7 '15 at 18:21
  • $\begingroup$ @DanBrumleve: Don't you need further specification/fixes for your equation? I don't think it is true for all n, p etc. I tested it for $ n = p = 3 $ and didn't work. (I hope, I didn't a calculation error in my head) $\endgroup$ – Imago Jan 7 '15 at 18:45
  • $\begingroup$ Another way of thinking about it: you want to find an $n$ such that $2^n \equiv_p n$. Then by Dan's comment, you have infinitely many. $\endgroup$ – dalastboss Jan 7 '15 at 18:45
  • $\begingroup$ I don't doubt, it works for infinity many cases :) just that one might need specification for n and p; $\endgroup$ – Imago Jan 7 '15 at 18:48
  • $\begingroup$ The specification is that $p \mid 2^n - n$. When $n = p = 3$ this is saying that $3 \mid 5$ which is not true, which is why that case does not work. $\endgroup$ – dalastboss Jan 7 '15 at 18:53

Let $o:=ord(2,p)$ be the smallest positive number with $2^o\equiv 1\ (\ mod\ p\ )$

Then we have for every natural number $k$ : $2^{ok}\equiv 1\ (\ mod\ p\ )$

Because of $1 < o < p$ there exists $q$ with $oq\equiv 1\ (\ mod\ p\ )$

So we have $2^{oq}\equiv oq\equiv 1\ (\ mod\ p\ )$

  • $\begingroup$ +1. I don't know German but your argument is clear anyway. $\endgroup$ – Matt Samuel Jan 7 '15 at 19:33
  • 1
    $\begingroup$ For a second I was confused as to whether I had accidentally stumbled upon a German version of stackexchange $\endgroup$ – Dasherman Jan 7 '15 at 19:35
  • 2
    $\begingroup$ @Dasherman it does say in the FAQ that if you're not confident writing in English it's better to write in a language you are comfortable with because someone will probably be able to translate it. $\endgroup$ – Matt Samuel Jan 7 '15 at 19:38

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.