SOLUTION TO PROBLEM 11

We will first determine the number of integers x in the range $1\leq x\leq 10000$ such that 2^x-x² is divisible by 7. Subtracting this number from 10000 then gives the answer to the problem.

Now 2^x-x² is divisible by 7 if and only if 2^x and x² both leave the same remainder when divided b 7. So it is natural to study these remainders. They both keep repeating as specified by the following claim.

Claim:         For every positive integer x:

(a)

2^x and 2^x+3 have the same remainder when divided by 7, and

(b)

x² and (x+7)² have the same remainder when divided by 7.

Proof of the Claim:         (a)    Note that $2^{x+3}-2^x=8\cdot 2^x-2^x=7\cdot 2^x$ is a multiple of 7.
(b)    This is because (x+7)²-x²=14x+49=7(2x+7) is a multiple of 7.

Investigating the first couple of cases we see that the possible remainders of 2^x when divided by 7 are 2, 4, and 1, and they keep repeating with a period of 3 (by Claim 1(a)). Similarly, by Claim 1(b) and investigation of initial cases, the reminders of x² when divided by 7 keep repeating with period of 7 and the cycle is 1, 4, 2, 2, 4, 1, 0.

Combining these observations, we see that the remainders of both 2^xand x² will repeat after a period of $3\cdot 7=21$. A tabulation of the first 21 values of x is given by the following chart:

$$\begin{tabular}{\vert c\vert c\vert c\vert c\vert c\vert c\ve... ...&2&2&4&1&0&1&4&2&2&4&1&0&1&4&2&2&4&1&0\\ \hline \end{tabular}$$

There are 6 cases in this range where 2^x-x² is divisible by 7 (namely x=2,4,5,6,10,15). By periodicity the next 21 values of x will give 6 more cases, and so on. Now $10000=21\cdot 476+4$, so the integers from 1 to 10000 split into 476 groups of 21 and 4 extra numbers at the end. The 476 groups contribute $476\cdot 6=2856$ values of x, and the remaining four numbers contribute 2 values of x(namely, x=9998 and x=10000). So the total is 2858; subtracting this from 10000 we get 10000-2858=7142 values of x for which 2^x-x² is not divisible by 7.

Questions and/or comments should be directed to Judy Downey or Griff Elder

    Back to the Problem of the Week Page
 
 

Last modified:   Sat Nov 10 13:33:29 CST 2001