Answer to Question #260140 in Discrete Mathematics for harsh

Question

Use the Well Ordering Principle to prove that any integer greater than or equal to 23 can be represented as the sum of nonnegative integer multiples of 6, 7 and 17.

Answer 1

Let $S(n)$ be the proposition that $n$ can be represented as the sum of nonnegative integer multiples of 6, 7 and 17.

Let $C=\{n\geq 23\ |\ S(n) \ \text{is false}\ \}$ .

We assume that $C$ is nonempty.

Then by the Well Ordering Principle, there is a smallest number, $m\in C$ .

$23=17+6\\ 24=6\cdot 4 \\ 25=6\cdot 3+7\\ 26=6\cdot 2+7\cdot 2 \\ 27=6+7\cdot 3 \\28=7\cdot 4$

Therefore, $m\geq29$ .

Since $m>m-6\geq 23$ , it follows that $(m-6)\not\in C$ and $S(m-6)$ is true.

But if $S(m-6)$ is true, then $S(m)$ must be true. Contradiction.

(if $n$ can be represented as the sum of nonnegative integer multiples of 6, 7 and 17, then we can add 6 and get representation for number $n+6$ )

So, $C$ is empty and $S(n)$ is true for $n\geq 23$ .