Determine the Set of a Sum of Numbers

Solution 1:

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.

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

Solution 2:

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.