prove that any integer greater than or equal to 8 can be represented as the sum of nonnegative integer multiples of 3 and 5

This problem asks to use Well Ordering Principle to prove any integer greater than or equal to 8 can be represented as the sum of nonnegative integer multiples of 3 and 5.

Here's where I'm at:

For the sake of contradiction assume that there is a nonempty set C such that, C :: = {n >= 8 (only positive integers) | n CAN'T be represented as a linear combination of 3 and 5}

By WOP C contains a least element m. m >= 9 because n=8 can be represented as a linear combination of 3 and 5.

I'm stuck here. I have to find a contradiction that shows C is an empty set but not sure how to approach this. Any hints? Thanks.

• "prove that any integer greater than or equal to 8 can be represented as$\ldots$" could be construed as "Pick any integer greater than or equal to 8 and prove that it can be represented as$\ldots$". But I don't think that's what you mean. Just say "every" instead of "any" and all ambiguity vanishes. Commented Aug 10, 2014 at 22:27
• Show this minimal criminal can't be $\gt 10$, and then show it is not $8$, $9$, or $10$.. Commented Aug 10, 2014 at 22:31
• @MichaelHardy What is the difference between saying "Prove that every integer $\geq 8$..." and "Prove that any integer $\geq 8$..."? I am not the original poster of the problem, but I am confused by how saying "every" changes the problem Commented Aug 10, 2014 at 22:31
• @user46944 : "Pick any card" does not mean "Pick every card". "Prove that any X is Y" can similarly mean "Pick any X and prove that it is Y". But "Any X is Y" without further context means "Every X is Y". But "Prove that every X is Y" cannot mean "Pick any X and prove that it is Y". ${}\qquad{}$ Commented Aug 10, 2014 at 23:04

If $m$ can't be represented as a sum of non-negative integer multiples of $3$ and $5$, then neither can $m-3$. Therefore $m$ cannot be greater than $10$, as if $m \geq 11$ then $m-3 \geq 8$, and thus $m-3$ would be in $C$, contradiction since $m$ is the least element of $C$. Now we just check the few remaining cases, which are $m=8,9,10$.

• Just note that this argument nicely generlizes if we replace the symbols $3,5,8$ with $a,b,a+b$; in which case: every number at least $a+b$ can be written as a multiple of $a$ and $b$. Also, the remaining cases would then be the integers from $a+b$ upto $a+b+min\{a,b\}-1$ (I think!). Commented Aug 11, 2014 at 19:16
• @Moses Not true. For example, if $a=2$ and $b=4$ then you can only get even numbers. If $a$ and $b$ are relatively prime then this will probably work. Commented Aug 12, 2014 at 0:23
• Good call! Maybe just an even-odd pair suffices, rather than relatively prime. I dunno; nonetheless, good thoughts :) Commented Aug 12, 2014 at 16:11
• The OP's example is not even-odd. Also, $12$ and $15$ cannot give you $28$, for example; $12$ and $15$ have $3$ as a common factor, so they only generate a subset of the multiples of $3$. Commented Aug 12, 2014 at 22:47
• Neat, so relatively prime may be it :) Commented Aug 13, 2014 at 21:32

As soon as you can represent three consecutive integers as $3x+5y$, you can represent them all by just adding a $3$ to the previous representations. Since $8=3+5,9=3+3+3$ and $10=5+5$, all the integers $\geq 8$ can be represented.

Another way to prove this is to consider that: $$r(n)=|\{(a,b)\in\mathbb{N}^2:3a+5b=n\}|$$ is the coefficient of $x^n$ in the product: $$(1+x^3+x^6+x^9+\ldots)(1+x^5+x^{10}+\ldots),$$ hence: $$\begin{eqnarray*}r(n)&=&[z^{n}]\frac{1}{(1-z^3)(1-z^5)}\\&=&[z^n]\left(\frac{1}{15(1-z)^2}-\frac{1}{5(1-z)}+h(z)\right)\end{eqnarray*}\tag{1}$$ where: $$h(z) = \sum_{\xi\in Z}\frac{\operatorname{Res}\left(\frac{1}{(1-z^3)(1-z^5)},z=\xi\right)}{\xi-z}$$ and $Z=\left\{\exp\frac{2\pi i}{3},\exp\frac{4\pi i}{3},\exp\frac{2\pi i}{5},\exp\frac{4\pi i}{5},\exp\frac{6\pi i}{5},\exp\frac{8\pi i}{5}\right\}$. Since the sum of the residues is $0$, the contribute to the coefficients given by the residues in $Z$ can never exceed $\frac{|Z|}{5}=\frac{6}{5}$. Hence we just need to prove that for any $n\geq N$, $$[z^n]\left(\frac{1}{15(1-z)^2}-\frac{1}{5(1-z)}\right)>\frac{6}{5}$$ holds, in order to prove that any $n\geq N$ can be represented as $3x+5y$. However: $$[z^n]\left(\frac{1}{15(1-z)^2}-\frac{1}{5(1-z)}\right)=\frac{n+1}{15}-\frac{1}{5},$$ hence we can take $N=21$ and fill the remaining cases ($n\in[8,20]$) by hand.

My proof is similar to Gyu Eun Lee's:

Let S(n) be the proposition that n is an integer greater than or equal to 8, and P(n) be the proposition that n can be written as integer multiples of 3 and 5.
Let C be the set of counterexamples, C::={n | S(n) and NOT(P(n))}. By W.O.P, there exists a smallest element in C, call it m. We verify P(8), P(9), P(10), so m must be greater than 10 to be a counterexample. Then the number (m-3) is greater than or equal to 8 and less than m, so P(m-3) holds; it follows P(m) must hold as well (m is (m-3) plus a multiple of 3), contradicting NOT(P(m)). Thus C is in fact empty.

Can we do it as follows?

1. Let P(n) = for all natural number n >= 8, exists k_1, k_2 such that n = 3k_1 + 5k_2
2. Let C = {n >=8|NOT(P(n))}
3. Assume C is not empty. By well ordering principle, there exists a smallest element d in C.
4. d does not equal to 3k_1 + 5_k2 for any integer k_1, k_2
5. check: P(8),P(9),P(10) holds, so d > 10.
6. d > d - 1 >= 8
7. so d - 1 = 3k_1 + 5k_2 for some k_1, k_2
8. then d = d - 1 + 1 = 3k_1 + 5k_2 + (6 - 5) = 3(k_1 + 2) + 5(k_2 - 1). A contradiction

Let P(t) is the property that for every $$t \geq 8$$ there are exist $$k_1,k_2$$ such that $$t = 3k_1 + 5k_2$$.

Let C be the set : C ::= {t $$\in N$$ || NOT(P(t))}.

For the purpose of obtaining contradiction we assume that C is not empty.

There is the smallest element, $$t_0 \in C$$

$$t_0 \geq 11$$ since P(8),P(9),P(10) holds.

We have that :

$$t_0 - 1 = 3k_1 + 5k_2$$

$$t_0 = 3(k_1 + 2) + 5(k_2 - 1)$$

which contradicting the fact that $$t_0$$ can not be written as a linear combination of 3 and 5

$$->$$ C is empty

• I see him/her stuck at proving this question when using WOP and i want to check whether my answer is correct Commented Jul 10, 2021 at 4:31