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>0$, such that
$$pN + qN = [K,K+1,...).$$
My question is, given $p$ and $q$, can we get a upper bound on $K$?
 A: Here is a $3$-line  arithmetical proof (with geometric view). For variety, below is an inductive variant. Let $f(x,y) = p\,x+q\,y.\,$ By $\,p,q\,$ coprime & Bezout $f(a,b)=pa+qb=1\,$ for some integers $\,a,b.\,$  Wlog we may assume that  $\,\color{#c00}{-q < a}< 0\, $ (so $\,\color{#0a0}{b>0})\,$ by choosing $\,a = (p^{-1}\!\bmod q) \color{#c00}{- q}$.
From base case $\,f(0,p) = pq\,$ we inductively apply: $ $ if $\,f(x,y) = n \ge pq\,$ with $\,x,y\ge0\,$ then there are $\,\bar x,\bar y >0\,$ with $\,f(\bar x,\bar y) = n\!+\!1,\,$  by adding $\,(a,b)\,$ to $\,(x,y)\,$ to increment $\,n,$ then if  $\,a\!+\!x \le 0,\,$ add $\,(q,-p)\,$ to force $\,\bar x,\bar y>0.\,$ We prove it works, using $\,f\,$ is linear & increasing.
$x\! +\! a > 0\Rightarrow f(\bar x,\bar y)\!=\! f(x\!+\!a,y\!+\!b) = f(x,y)\!+\!f(a,b) = n\!+\!1,\,$ & $\, y\ge0,\color{#0a0}{b>0}\Rightarrow y\!+\!b>0$
$y\!+\!b > p\Rightarrow f(\bar x,\bar y) \!=\!f(x\!+\!a\!+\!q,y\!+\!b\!-\!p)=f(x,y)\!+\!f(a,b)\!+\!f(q,-p) = n\!+\!1\!+\!0,\,$ and $\,x\ge0,\,\color{#c00}{a\!+\!q}>0\Rightarrow x\!+\!a\!+\!q>0.\,$ This case must hold if the prior fails, else both fail so
$\begin{align}&x\!+\!a\le 0\\ &y\!+\!b\,\le p\end{align}\Rightarrow\,  f(x\!+\!a,y\!+\!b)\le f(0,p)\,$ i.e $\:n\!+\!1 \le pq,\,$ contra $\,n \ge pq\,$ by hypothesis.

Example $ $ Let $\,f(x,y)=17x+23y.\,$ The gcd Bezout identity here is $\,f(-4,3)=1\,$ so if $\,f(x,y) = n\,$ then we can add $1$ via  $\,f(x-4,y+3) = f(x,y)+f(-4,3) = n+1,\,$ and if  $\,\color{#c00}{x-4\le 0}\,$ then we can make it $> 0$ by further $\rm\color{#c00}{adding\  (23,-17)},\,$ since $\,f(23,-17)=0,\,$ so
$391 = f(\ \ \ 0,17),\ $ so adding $1 = f(-4,3)\,$ yields
$392 = f(\color{#c00}{-4},20) = f(19,3)$ by $\rm\color{#c00}{adding\  (23,-17)}$
$393 = f(\  15,6)$
$394 = f(\  11,9)$
$395 = f(\ \ \ 7,12)$
$396 = f(\ \ \ 3,15)$
$397 = f(\color{#c00}{-1},18) = f(22,1)$
Remark $ $ A unit shift transforms to the case of nonnegative (vs. above) positive  solutions $\,x,y$.
There is much literature on this classical problem. To locate such work
one should search on the many aliases,
e.g. postage stamp problem, Sylvester/Frobenius coin problem,
Diophantine problem of Frobenius, Frobenius conductor,
money changing, coin changing, change making problems, chicken McNugget theorem, h-basis and asymptotic bases in additive number theory,
integer programming algorithms and Gomory cuts,
knapsack problems and greedy algorithms, etc.
A: $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.
A: 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).
