Divisibility of $2^n-n^2$ by 7 How many positive integers $n<10^4$ are there such that $2^n - n^2$ is divisible by 7?  
 A: Just write out periods:
$2^n:2,4,1,2,4,1,2,4,1,2,4,1,2,4,1,2,4,1,2,4,1,|2...$ with period $3$
$n^2:1,4,2,2,4,1,0,1,4,2,2,4,1,0,1,4,2,2,4,1,0,|1...$ with period $7$
So in every $21$ numbers there are $6$ numbers.
Now just calculate $10^4\over 21$$=476$ and since $10000$ itself is not included there are $3$ remainder left so totally $6\cdot476+1=2857$ numbers.
A: $10^4$ is small enough that it is possible to write a computer program to find the answer, but it is also possible to solve explicitly as follows:
We note that the possible remainders of $n^2$ modulo $7$ are $0, 1, 2$ and $4$. Since $2^n$ is never divisible by $7$, the possibilities that we have for which $2^n-n^2$ is divisible by $7$ are
$$ 2^n \equiv 1 \pmod 7 \quad\text{ and }\quad n \equiv \pm 1 \pmod 7$$
or
$$ 2^n \equiv 2 \pmod 7 \quad\text{ and }\quad n \equiv \pm 3 \pmod 7$$
or
$$ 2^n \equiv 4 \pmod 7 \quad\text{ and }\quad n \equiv \pm 2 \pmod 7$$
Now $2^n \equiv 1 \pmod 7$ if and only if $n \equiv 0 \pmod 3$, $2^n \equiv 2 \pmod 7$ if and only if $n \equiv 1 \pmod 3$, and $2^n \equiv 4 \pmod 7$ if and only if $n \equiv 2 \pmod 3$.
So our possibilities are
$$
\begin{align*}
  n & \equiv 0 \pmod 3 && \text{and} & n & \equiv 1 \pmod 7 \\
  n & \equiv 0 \pmod 3 && \text{and} & n & \equiv -1 \pmod 7 \\
  n & \equiv 1 \pmod 3 && \text{and} & n & \equiv 3 \pmod 7 \\
  n & \equiv 1 \pmod 3 && \text{and} & n & \equiv -3 \pmod 7 \\
  n & \equiv 2 \pmod 3 && \text{and} & n & \equiv 2 \pmod 7 \\
  n & \equiv 2 \pmod 3 && \text{and} & n & \equiv -2 \pmod 7
\end{align*}
$$
We can use the Chinese Remainder Theorem to find the solution to each pair of equations. We find that the possibilities for $n$ modulo $21$ are $15, 6, 10, 4, 2$ and $5$. Or, in order: $2, 4, 5, 6, 10, 15$ and $21$.
We now just need to count how many numbers there are with each remainder up to $10^4$. We have that $10^4 = 476 \times 21 + 4$, and so there are $476$ complete sets of $21$ numbers up to $10^4$, and $4$ extra. We find that the answer is $476 \times 6 + 1$ (Not $+2$ since we exclude $10^4$ since $n$ is strictly less than $10^4$) This is equal to $2857$.
