When do the multiples of two primes span all large enough natural numbers?

$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.

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.\,$ We may assume that $\,\color{#c00}{-q < a}< 0\, $ (hence $\,\color{#0a0}{b>0})\,$ by choosing $\,a = (p^{-1}\!\bmod q) - 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 our new $\,\bar x,\bar y>0.\,$ Let's prove it works, using $\,f(x,y)\,$ 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, by both can't fail, i.e.

$\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.

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 you should ensure that you 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, h-basis and asymptotic bases in additive number theory, integer programming algorithms and Gomory cuts, knapsack problems and greedy algorithms, etc.