<s>[INST] The number $85^9 - 21^9 + 6^9$ is divisible by an integer between 2000 and 3000. Compute that integer. 
The number $85^9 - 21^9 + 6^9$ is divisible by an integer between 2000 and 3000. Compute that integer.


I tried taking the expression mod 5, 7, etc. getting a few congruences, but nothing that led to an answer between 2000 and 3000. Note that I am not allowed to use a calculator or a computer.
Euler's Theorem might also lead to an answer.
 [/INST] To elaborate on the trial division approach, we can observe that $$85^9 - 21^9 = (85-21)(85^8 + 85^7 21^1 + \cdots + 21^8), \tag{1}$$ thus this part is divisible by $85 - 21 = 64 = 2^6$.  Then $6^9 = 2^9 \cdot 3^9$, hence we know $2^6$ divides the entire number $N = 85^9 - 21^9 + 6^9$.  We know $2$ does not divide the second factor in the difference of ninth powers in equation $(1)$, because all of the terms in that factor are odd, and there are an odd number of terms.  Therefore $2^6$ is the largest power of $2$ that divides $N$.
As for modulo $3$, the first term $85^9$ is not divisible by $3$ since $85$ is not divisible by $3$, but the other two terms are, so we are done there.
For modulo $5$, the first term is clearly divisible.  The second term is $-1$ mod $5$ since $21 \equiv 1$, hence $-21^9 \equiv -1$. The third term has $6 \equiv 1$.  So $N$ is divisible by $5$.  If we check mod $7$, then we won't need to consider mod $5^2$.
For modulo $7$, $85 \equiv 1$ and $6 \equiv -1$, and $21 \equiv 0$; thus by similar reasoning as above, $N$ is divisible by $7$, and we are done.
</s>