A positive integer $k$ when divided by the prime number $p$ leaves a remainder of 6. We get the same remainder when dividing $1000 - k$ by $p$; we also know that $10000 - k$ is divisible by $p$. Which is this prime number $p$?
Solution. Let's write down the divisions with remainders:

$$
\begin{aligned}
k & =x \cdot p+6 \\
1000-k & =y \cdot p+6 \\
10000-k & =z \cdot p
\end{aligned}
$$

where $x, y, z$ are non-negative integers. Subtract the difference of the first two equations from twice the third equation:

$$
\begin{aligned}
(20000-2 k)-(1000-2 k) & =2 z p-(y p+6-x p-6) \\
19000 & =2 z p+(x-y) p \\
19000 & =(x-y+2 z) p
\end{aligned}
$$

Thus, $p \mid 19000$. Since $19000=2^{3} \cdot 5^{3} \cdot 19$ and since 6 appeared as a remainder when dividing by $p$, $p$ can only be larger than this prime, so the only possible prime is $p=19$. For example, if $k=500$, then all conditions are satisfied, so $p=19$.