# 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

5
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

## 3 Answers

$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$. – Byron Schmuland Oct 28 '10 at 15:16

1
@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

1
@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

1
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
show 1 more comment

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 29, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9245948791503906, "perplexity_flag": "middle"}