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$
$\endgroup$
-
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
3
$\begingroup$
$\endgroup$
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
