Divisibility of $2^n-n^2$ by 7

Question

How many positive integers $n<10^4$ are there such that $2^n - n^2$ is divisible by 7?

Answer 1

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.

Answer 2

$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$.