Coloring integers

Residues. There are $k$ residues mod $k$, and $k$ colors. If each color contains at most one residue, we can assign one residue to each color — possible only if there are exactly $k$ integers.

For $k+1$ integers. By pigeonhole, two have the same residue mod $k$, i.e. their difference is divisible by $k$.

Conclusion. With more than $k$ integers, two same-color integers have difference divisible by $k$.