When do the multiples of two primes span all large enough natural numbers? It is well-known that given two primes $p$ and $q$, $pZ + qZ = Z$  where $Z$ stands for all integers.
It seems to me that the set of natural number multiples, i.e. $pN + qN$ also span all natural numbers that are large enough. That is, there exists some $K&gt;0$, such that
$$pN + qN = [K,K+1,...).$$

My question is, given $p$ and $q$, can we get a upper bound on $K$?
$K = pq + 1$ if $\mathbb{N} = \{ 1, 2, 3, ... \}$, and $K = pq - p - q + 1$ if $\mathbb{N} = \{ 0, 1, 2, 3, ... \}$.  This is known as the coin problem, or Frobenius problem (and you only need $p, q$ relatively prime).  It frequently appears on middle- and high-school math competitions.

Edit:  I completely misremembered how hard the proof is.  Here it is.  If $n$ is at least $pq+1$, then the positive integers

$$n-p, n-2p, ... n-qp$$

have distinct residue classes $\bmod q$, so one of them must be divisible by $q$.  On the other hand, it's not hard to see that $pq$ itself cannot be written in the desired way.
This follows easily by Bézout's lemma (as Qiaochu notes, x and y only need to be coprime to generate the unit ideal (indeed, this is the proper generalization of the term "coprime")).  

We can ever so-slightly strengthen this to show that $\mathbf{Z}$ is a PID (this is the true content of Bézout's lemma).