Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
"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$.

share|cite|improve this answer
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.

share|cite|improve this answer
+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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.