# 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$?

#### Solutions Collecting From Web of "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.

HINT $\rm\ \ p\ (p^{-1}\: mod\ q) + q\ (q^{-1}\: mod\ p)\ =\ pq+1\$ since it’s $1$ mod $\rm\:p,q\:$ and $\rm >2\:$ and $\rm < 2\:pq$

To represent largers numbers keep adding $\rm\ 1 = ap+bq\$ while, if need be, adding $\rm\:\pm (q ,-p)\:$ to the coefficients to keep them positive.

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