Question

How many positive integers $x\le 10000$ are there such that the difference $2^x-x^2$ is not divisible by 7?

• A. 6662
• B. 7142
• C. 3687
• D. 7562

Answer 1

The correct option is B

7142

$2^x-x^2$ is divisible by 7 if and only if $2^x$ and $x^2$ both leave the same remainder when divided by 7.

$\begin{array}{ccc}x& 2^x& Remainderwith7\\ 1& 2& 2\\ 2& 4& 4\\ 3& 8& 1\\ 4& 16& 2\\ 5& 32& 4\\ 6& 64& 1\\ 7& 128& 2\\ 8& 256& 4\end{array}$

$\begin{array}{ccc}x& x^2& Remainderwith7\\ 1& 1& 1\\ 2& 4& 4\\ 3& 9& 2\\ 4& 16& 2\\ 5& 25& 4\\ 6& 36& 1\\ 7& 49& 0\\ 8& 64& 1\\ 9& 81& 4\\ 10& 100& 2\end{array}$

Remainder of $2^x$ repeats after every 3 and remainder of $x^2$ repeats after 7. The remainders of both $2^x$ and $x^2$ will repeat after a period of length 3$\times$7 = 21

$\begin{array}{cccccccccccccccccccccc}x& 1& 2& 3& 4& 5& 6& 7& 8& 9& \frac{1}{0}& \frac{1}{1}& \frac{1}{2}& \frac{1}{3}& \frac{1}{4}& \frac{1}{5}& \frac{1}{6}& \frac{1}{7}& \frac{1}{8}& \frac{1}{9}& \frac{2}{0}& \frac{2}{1}\\ \underset{x}{2}& 2& 4& 1& 2& 4& 1& 2& 4& 1& 2& 4& 1& 2& 4& 1& 2& 4& 1& 2& 4& 1\\ x^2& 1& 4& 2& 2& 4& 1& 0& 1& 4& 2& 2& 4& 1& 0& 1& 4& 2& 2& 4& 1& 0\end{array}$

In this set of 21 values, we see that there are 6 values of x for which the remainders are same.

As per the periodicity, within every consecutive 21 values, 6 will repeat.

10,000 = 21$\times$476 + 4

The 476 groups contribute 476$\times$6 = 2856 values and the remaining 4 will give 2 values.
So, total 2858 integers $\le 10000$ are divisible. Thus, 10000- 2858 = 7142 integers are not divisible.