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

• I assume you mean pN + qN contains [K, K+1, ...). It's not hard to see that below K there are gaps. – Qiaochu Yuan Oct 28 '10 at 15:01
• This works the same whether p and q are prime or not, as long as their greatest common divisor is 1. – Ross Millikan Oct 28 '10 at 15:58

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

• Qiaochu: Typo? $K=pq-p-q+1$. – user940 Oct 28 '10 at 15:16
• @Byron: this would be true if the OP is allowing non-negative integer multiples, but the OP wants positive integer multiples. – Qiaochu Yuan Oct 28 '10 at 15:19
• @Qiaochu: the OP said "nautral numbers". Please tell me you're not one of those misguided souls who doesn't think $0$ is a natural number! (More seriously, you should probably clarify this in your response. You might as well give the answer both ways.) – Pete L. Clark Oct 28 '10 at 16:22
• @Pete: I'm agnostic. Generally I use Z_{\ge 0} for the non-negative integers. I'll add the clarification. – Qiaochu Yuan Oct 28 '10 at 16:29
• Nice answer. However, to ensure that the coefficient of p is positive, I think you should be saying that n-p,n-2p,...,n-qp have distinct residue classes mod q. – George Lowther Nov 6 '10 at 20:59

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