Problem (Number Theory):
$\quad$ Compute the greatest integer $k \leq 1000$ such that $\left(\begin{array}{c}1000 \\ k\end{array}\right)$ is a multiple of 7 .

Solution:
The ratio of binomial coefficients $\left(\begin{array}{c}1000 \\ k\end{array}\right) /\left(\begin{array}{c}1000 \\ k+1\end{array}\right)=\frac{k+1}{1000-k}$. Because 1000 is 1 less than a multiple of 7 , namely $1001=7 \cdot 11 \cdot 13$, either $1000-k$ and $k+1$ are both multiples of 7 or neither is. Hence whenever the numerator is divisible by 7, the denominator is also. Thus for the largest value of $k$ such that $\left(\begin{array}{c}1000 \\ k\end{array}\right)$ is a multiple of $7, \frac{k+1}{1000-k}$ must equal $7 \cdot \frac{p}{q}$, where $p$ and $q$ are relatively prime integers and $7 \nmid q$. The only way this can happen is when $k+1$ is a multiple of 49 , the greatest of which less than 1000 is 980 . Therefore the greatest value of $k$ satisfying the given conditions is $980-1=\mathbf{9 7 9}$.

Rewrite 1000 in base 7: $1000=2626_{7}$. Let $k=\underline{a} \underline{b} \underline{c}_{7}$. By Lucas's Theorem, $\left(\begin{array}{c}1000 \\ k\end{array}\right) \equiv\left(\begin{array}{l}2 \\ a\end{array}\right)\left(\begin{array}{l}6 \\ b\end{array}\right)\left(\begin{array}{l}2 \\ c\end{array}\right)\left(\begin{array}{l}6 \\ d\end{array}\right) \bmod 7$. The binomial coefficient $\left(\begin{array}{l}p \\ q\end{array}\right) \stackrel{a}{=} 0$ only when $q>p$. Base 7 digits cannot exceed 6 , and $k \leq 1000$, thus the greatest value of $k$ that works is $2566_{7}=\mathbf{9 7 9}$. (Alternatively, the least value of $k$ that works is $30_{7}=21$; because $\left(\begin{array}{l}n \\ k\end{array}\right)=\left(\begin{array}{c}n \\ n-k\end{array}\right)$, the greatest such $k$ is $1000-21=979$.)

Final answer: 979