Determine the Set of a Sum of Numbers

I want to determine the set of natural numbers that can be expressed as the sum of some non-negative number of 3s and 5s.

$$S=\{3k+5j∣k,j∈\mathbb{N}∪\{0\}\}$$

I want to check whether that would be: 0,3, 5, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, and so on.

Meaning that it would include 0, 3, 5, 8. Then from 9 and on, every Natural Number. But how would I explain it as a set? or prove that these are the numbers in the set?

• This is a case of the Frobenius coin problem, discussed at en.wikipedia.org/wiki/Coin_problem – Ross Millikan Oct 5 '11 at 13:55
• I forgot to mention that 6 can be made too., so 0, 3, 5, 6, then from 9 and beyond. – Salazar Oct 5 '11 at 14:17

You can write $$S = \{0,3,5\} \cup \{n\in\mathbb{N}:n\ge 8\}.$$ You can also write $$S = (\mathbb{N}\cup\{0\})\setminus \{1,2,4,7\}.$$

Once you know that $8,9,10\in S$, you can prove that every natural number $n\ge 8$ belongs to $S$ by showing that if $n\ge 8$, there is a non-negative integer $k$ such that $n$ is $3k+8$, $3k+9$, or $3k+10$: then you can start with $3$’s and $5$’s adding up to $8$, $9$, or $10$ and add $k$ more $3$’s.

HINT: Look at the quotient and remainder when you divide $n$ by $3$.

This doesn't tell you exactly which numbers can be written as $3k+5j$ with $j,k\ge0$, but it might be the best that can be said in general. These are two Theorems that usually accompany Bezout's Identity.

Theorem $\boldsymbol{1}$: Suppose $\operatorname{gcd}(a,b)=1$ and $c \ge (a-1)(b-1)$. Then $ax+by=c$ has a non-negative solution, that is, one in which both $x$ and $y$ are non-negative integers.

Proof of Theorem $\boldsymbol{1}$:
Since $gcd(a,b)=1$, we have some $(u,v)$ so that $au+bv=1$. The set of all solutions to $ax+by=c$ is $\{ (cu+bk,cv-ak) : k \in Z \}$. Thus, we have a non-negative solution $(x,y)$, i.e. one in which both $x$ and $y$ are non- negative, precisely when there is an integer $k$ so that $k \ge -cu/b$ (so that $cu+bk \ge 0$) and $k \le cv/a$ (so that $cv-ak \ge 0$). Thus, $ax+by=c$ has a non-negative iff there is an integer in $[-cu/b,cv/a]$.

Suppose there is no integer in this interval. This means that it must be contained in some interval $(j,j+1)$. Since $cu$ and $cv$ are integers, we must have $$-cu/b-j \ge 1/b\tag{1a}$$ and $$j+1-cv/a \ge 1/a\tag{1b}$$ Adding $(1a)$ and $(1b)$ and multiplying by $ab$ gives $$ab-cau-cbv \ge a+b\tag{1c}$$ Since $au+bv=1$, $(1c)$ becomes $$c \le ab-a-b\tag{1d}$$ Therefore, if $c \ge ab-a-b+1 = (a-1)(b-1)$, then there is a non-negative solution $(x,y)$ to $ax+by=c$. $$\square$$

Theorem $\boldsymbol{2}$: Suppose $\operatorname{gcd}(a,b)=1$, $0 \lt c \lt ab$, and neither $a\mid c$ nor $b\mid c$. Then one and only one of $$ax+by=c\tag{2a}$$ and $$ax+by=ab-c\tag{2b}$$ has a non-negative solution.

Proof of Theorem $\boldsymbol{2}$:
Note that since neither $a\mid c$ nor $b\mid c$, neither $x$ nor $y$ can be $0$ in any solution. Therefore, any non-negative solution must be a positive solution, that is, one in which both $x$ and $y$ are positive integers.

Suppose both $as+bt=c$ and $au+bv=ab-c$ are positive solutions. Add them together to get $$a(s+u)+b(t+v) = ab\tag{2c}$$ Since $gcd(a,b)=1$, $(2c)$ says that $b|s+u$ and $a|t+v$. Since $s$, $t$, $u$, and $v$ are positive integers, we must have that $s+u\ge b$ and $t+v\ge a$. However, then $a(s+u)+b(t+v) \ge 2ab$, which contradicts $(2c)$.

Therefore, we have shown that at most one of $(2a)$ and $(2b)$ can have a non-negative solution.

Suppose $(2a)$ does not have a non-negative solution. Since $gcd(a,b)=1$, we have some $(u,v)$ so that $au+bv=1$. The set of all solutions to $ax+by=c$ is then $\{ (cu+bk,cv-ak) : k \in Z \}$. Therefore, we can find an $(s,t)$ so that $as+bt=c$ and $0 \le s \lt b$.

Since $bt = c-as$, we have that $-ab \lt bt \lt ab$. Since $(2a)$ does not have a non-negative solution, we must have $-ab \lt bt \lt 0$. Thus, we have the non-negative solution $a(b-s)+b(-t) = ab-c$.

Therefore, we have shown that at least one of $(2a)$ and $(2b)$ must have a non-negative solution. $$\square$$

• @robjohn Recalling from sci.math that you enjoyed Bezout-based proofs of the Rational Root Test, you might find interesting this proof by degree descent. – Bill Dubuque Dec 15 '11 at 5:04
• @robjohn: I'm reading your proof of Theorem 1 but cannot figure out the reason for the two inqualities (1a) and (1b), namely, why $-cu/b - j \ge 1/b$ and $j+1 - cv/a>=1$. Please explain it if possible because obviously this is the key. Thank you. – C. Y. Cheng Apr 8 '14 at 21:39
• @C.Y.Cheng: Since there is no integer in $[-cu/b,cv/a]$ we must have some $j$ so that $[-cu/b,cv/a]\subset(j,j+1)$. That means $j\lt-cu/b\lt cv/a\lt j+1$. Thus, $-cu/b-j\gt0$, but since $-cu-bj\gt0$ is an integer, it must be at least $1$. Therefore, $$-cu/b-j\ge1/b$$ Similarly, $j+1-cv/a\gt0$ and since $(j+1)a-cv\gt0$ is an integer, it must be at least $1$. Therefore, $$j+1-cv/a\ge1/a$$ – robjohn Apr 9 '14 at 2:26
• @robjohn: Thank you very much for your crystal clear explanation. The proof is valuable, and I really appreciate it. – C. Y. Cheng Apr 9 '14 at 4:10

By inspection, you can see how to represent 0, 3, 5, and 8. Now, given any integer $n \geq 9$, classify $n$ into one of the following cases.

Case $n \equiv 0$ (mod 3): In this case, $n = 3k$ for some $k$, so there is nothing to show (it is already a certain multiple of 3).

Case $n \equiv 1$ (mod 3): In this case, $n = 3k + 1$ for some $k \geq 3$ (since $n \geq 9$). We can write $n = 3(k-3) + 5 \cdot 2$.

Case $n \equiv 2$ (mod 3): In this case, $n = 3k + 2$, for some $k \geq 3$. We can write $n = 3(k-1) + 5$.

So, not only do all those numbers belong to the set, but there is an easy way to figure out how they are represented.

This type of a question falls under the umbrella of numerical semigroups. The numerical semigroup generated by a set of positive integers consists of their linear combinations with non-negative integer coefficients. So your set is the numerical semigroup generated by $\{3,5\}$.

I have encountered these as sets of 'pole numbers' of algebraic curves. In that context the 'gaps' (the numbers missing from the list) are related to the genus of the curve.

For example, it is known that, if $(a,b)=1$, then the number of gaps of the numerical semigroup generated by $\{a,b\}$ equals $(a-1)(b-1)/2$. This checks out in your case. You have $a=3,b=5$, so the number of gaps should be $(3-1)(5-1)/2=4$, and you have found all of them: $1,2,4,7$. It is also known (and not hard to prove) that the largest gap is $(a-1)(b-1)-1$. In your case $(3-1)(5-1)-1=7$.

• Theorem $2$ in my answer justifies this. There are $(a-1)(b-1)$ numbers between $0$ and $ab$ that are not multiples of $a$ or $b$, and of these, exactly one of $c$ or $ab-c$ permit a solution to $ax+by=c$. Theorem $1$ says that every $c\ge(a-1)(b-1)$ admits a solution. – robjohn Oct 5 '11 at 16:06
• @robjohn Indeed! Very nice! – Jyrki Lahtonen Oct 5 '11 at 18:26

First, it will be easier to determine the set $$I = \{3k+5j | k,j \in \mathbb{Z}\}.$$

This set is an ideal over $\mathbb{Z}$. That is, if $a,b \in I$ then $a+b \in I$ ($I+I \subset I$), and if $a \in I$ and $z \in \mathbb{Z}$, then $za \in I$ ($\mathbb{Z}I \subset I$).

The Euclidean algorithm allows on to prove that all ideals over $\mathbb{Z}$ are in fact the set of multiples of a sole number. Take $a \in I$, the smallest positive element of $I$, and let $b \in I$ be any other element. The Euclidean algorithm shows that there is a $q \in \mathbb{Z}$, and an integer $0 \leq r < a$ such that $$b = qa + r.$$ But since $I$ is an ideal, $r = b - qa \in I + \mathbb{Z}I \subset I$. From the minimality of $a$, we conclude that $r = 0$. That is, $I = a\mathbb{Z}$.

It is evident that all elements of $I$, including $a$, are multiples of $M = \mathrm{GCD}(3,5) = 1$. And again, the Euclidean algorithm shows that $M \in I$. That is, $a = M$. In the case of $3$ and $5$, $a = 1$. That is, $I = \mathbb{Z}$.

So, what we know is that every integer can be written as $3k + 5j$ for $k,j \in \mathbb{Z}$. Notice that we can add and subtract multiples of $15$: $3k + 5j = 3(k+n5) - 5(j-n3)$. Show that if $3k + 5j \geq 15$, then you can add and subtract a multiple of $15$ in order to end up with $j,k \geq 0$. That is, any integer greater then or equal to $15$ is in $S$. Now, you just have to check the integers between $0$ and $15$.

• Of course you don't need all of this... The Euclidean algorithm already implies that $1 = M \in I$. So you can conclude that $I = \mathbb{Z}$. But I really like the fact that Euclidean domains are principal ideal domains, that is every ideal is composed by the multiples of a number. – André Caldas Oct 5 '11 at 4:56