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$?
On
Here is a $3$-line arithmetical proof (with geometric view). Below is an inductive variant (highly recommended for motivation / warm-up: first browse cases $p,q\!=\!3,5$ and $p,q\!=\!17,23$ below).
Let $f(x,y) = px+qy.\,$ $f(a,b)=pa+qb=1\,$ for some $\,a,b\in\Bbb Z\,$ by Bezout & $\,p,q\,$ coprime. 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)},\,$ by $\,f(23,-17)=0,\,$ e.g.
$391 = f(\ \ \ 0,17)\ $
$392 = f(\color{#c00}{-4},20)\ \ \ $ by adding $\:\!1 = f(-4,3)\,$
$\qquad\! = f(\ 19,3)\ \ \ \ \ $ by $\color{#c00}{{\rm adding}\ 0 = f(23,-17)}\ $ to make $\,x>0$
$393 = f(\ 15,6)\ \ \ \ \ $ by adding $\ 1 = f(-4,3)$
$394 = f(\ 11,9)\ \ \ \ \ \ \ldots$
$395 = f(\ \ \ 7,12)$
$396 = f(\ \ \ 3,15)$
$397 = f(\color{#c00}{-1},18)$
$\qquad\! = f(\ \,22,1)\quad$ by $\color{#c00}{{\rm adding}\ 0 = f(23,-17)}\ $ to make $\,x>0$
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.
On
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).
$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.