Divisibility proof with co-prime numbers

Let $a,b$ be co-prime. Prove that for every integer $n > a$ it is true that $a | (n + kb)$ for some $k$ with $0 <= k < a$.

I have a feeling this is very basic stuff and I feel like there is a very simple intuitive proof and it's on the tip of my tongue but I just can't express it.

Answer

Recall that for any integers $a,b$ (not both zero) the extended Euclidean algorithm allows you to find integers $x,y \in \mathbb{Z}$ such that $ax+by=d$ where $d$ is the greatest common divisor of $a,b$.

So in your case, there exist $x,y \in \mathbb{Z}$ such that $ax+by=1$ (since $a,b$ are relatively prime). Thus $ax=1-by$. Multiply through by $n$ and you have your result. :)