Problem
COM-B2-M04-P010 Sums of Threes and Fives
#10
★★★☆☆ Level 3 of 5
Prove that every integer \(n\ge 8\) can be represented as \(n=3a+5b\), where \(a,b\) are nonnegative integers.
Check the first three numbers, then choose the smallest counterexample.
We have \(8=3+5\), \(9=3+3+3\), and \(10=5+5\). Suppose counterexamples exist, and let \(n\) be the smallest one.
Since \(8,9,10\) are representable, \(n\ge 11\). Then \(n-3\ge 8\), and by the minimality of \(n\), the number \(n-3\) is representable: \(n-3=3a+5b\).
Therefore \(n=3(a+1)+5b\), contradicting the fact that \(n\) is a counterexample. Hence the statement is true for all \(n\ge 8\).
Although the problem is numerical, the method is a pure minimal counterexample.