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