How many natural numbers $n$ not greater than $10000$ are there such that $2^n - n^2$ is divisible by $7$? How many natural numbers $n$ not greater than $10000$ are there such that $2^n - n^2$ is divisible by $7$?
Please help me solve this question!
 A: Hint. Since $2^3\equiv 1 \pmod {7}$, consider $n=3q+r$ with the remainder $r=0,1,2$. 
If $r=0$, then $1\leq q \leq 3333$ and 
$$0\equiv 2^n - n^2=1-9q^2\equiv 1-2q^2\implies q\equiv 2, q\equiv 5\pmod{7}$$
Therefore the number of $n=6q$ is equal to
$$\left\lfloor\frac{3333-2}{7}\right\rfloor+1+\left\lfloor\frac{3333-5}{7}\right\rfloor+1=952.$$
Now consider the remaining similar cases. At the end you should find that for $r=1,2$ the number of $n$s are respectively $953$, $953$. 
Therefore the answer should be $952+953+953=2858$.
A: We need $$2^n\equiv n^2\pmod7$$
Now for integer $n, n^2\equiv0,1\equiv8,2,4\pmod7$
For $n^2\equiv0\pmod7,$ we need $$2^n\equiv0\pmod7$$ which is untenable (why?)
For $n^2\equiv1\pmod7\iff n\equiv\pm1\ \ \ \  (1),$
we need $$2^n\equiv1\pmod7\iff n\equiv0\pmod3\ \ \ \  (2)$$
By $(1),(2): n\equiv6,15\pmod{21}$
For $n^2\equiv2\pmod7\iff n\equiv\pm3\ \ \ \  (3),$
we need $$2^n\equiv2\pmod7\iff n\equiv1\pmod3\ \ \ \  (4)$$
By $(3),(4): n\equiv10,4\pmod{21}$
For $n^2\equiv4\pmod7\iff n\equiv\pm2\ \ \ \  (5),$
we need $$2^n\equiv4\pmod7\iff n\equiv2\pmod3\ \ \ \  (6)$$
By $(5),(6): n\equiv2,5\pmod{21}$
So, the required number will be $$\sum_{r=\{6,1510,4,2,5\}}\left\lfloor\dfrac{10000-r}{21}\right\rfloor$$
