Infinitely many $n$ such that $2^n-n$ is divisible by a prime

Question

I found the following question and can't make much headway with it.

Show that there exist infinitely many positive integers $n$ such that $2^n \equiv n \mod p$ where $p$ is a odd prime...

I started by writing the number as $n=(p-1)k+c$ which implies $$2^c \equiv c-k \mod p$$ where I used Fermat's Little theorem. Now if $k$ is of the form $pm$ for some integer $m$ we get $n=(p-1)(p)m+c$ $$2^c \equiv c \mod p$$ and we have reduced $n$ to some smaller integer $c$ but I can't figure out how to find the smallest number $c$ which would then generate infinitely many $n$.

Any help in finding a possible approach to this would be highly appreciated.

Answer 1

A plan of attack. Justify the following claims:

• The remainder $r(n)$ of $2^n$ modulo $p$ repeats cyclically with period $\ell$, where $\ell$ is the smallest positive integer such that $2^\ell\equiv1\pmod p$. By Lagrange (or Little Fermat, really) $\ell$ is a factor of $p-1$. Anyway, $r(n+\ell)=r(n)$ for all $n$.
• The remainder $s(n)$ of $-n$ modulo $p$ repeats with a period $p$. In other words $s(n+p)=s(n)$ for all $n$.
• Therefore the sum sequence $z(n):=r(n)+s(n)$ repeats with a period $\ell p$ (observe that $\gcd(\ell,p)=1$). In other words $z(n+\ell p)=z(n)$ for all $n$.
• We have $s(2)\equiv-2\pmod p, r(1)=2$. By the Chinese remainder theorem there exists an integer $m$ such that $m\equiv2\pmod p$ and $m\equiv1\pmod\ell$. Show that $z(m)$ is divisible by $p$.
• Apply the third bullet to show that $z(n)$ is divisible by $p$ for infinitely many choices of $n$.

Answer 2

Consider the two sequences $a_n$ and $b_n$ of integers modulo $p$ given by $$ \begin{array}{c|cccc} n&1&2&3&\cdots\\\hline a_n&2^1& 2^2& 2^3& \cdots\\ b_n &1& 2& 3&\cdots \end{array} $$ One has (not necessarily fundamental) period $p-1$ by Fermat's little, the other has (fundamental) period $p$, which means that their periods will line up every possible way, infinitely many times in the above table. Add that to the fact that there are numbers which appear in both sequences, and that's a full solution to your problem.