# 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. – Michael Hardy Aug 10 '14 at 22:27
Show this minimal criminal can't be $\gt 10$, and then show it is not $8$, $9$, or $10$.. – André Nicolas Aug 10 '14 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 – user46944 Aug 10 '14 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{}$ – Michael Hardy Aug 10 '14 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!). – Musa Al-hassy Aug 11 '14 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. – Gyu Eun Lee Aug 12 '14 at 0:23
Good call! Maybe just an even-odd pair suffices, rather than relatively prime. I dunno; nonetheless, good thoughts :) – Musa Al-hassy Aug 12 '14 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$. – Gyu Eun Lee Aug 12 '14 at 22:47
Neat, so relatively prime may be it :) – Musa Al-hassy Aug 13 '14 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.

-
+1. Unexpected. – Felix Marin Aug 11 '14 at 23:07

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.

-