Solution

Prove that for $n>23$, there exists non-negative integers $x$ and $y$ such that $n=7x+5y$.


We shall argue by cases, proving each case with induction...

We have $5$ cases: $n$ could have remainder $0$, $1$, $2$, $3$, or $4$ upon division by $5$.

Establishing the basis step for cases involving remainders of $4$, $0$, $1$, $2$, and $3$ (in that order), we observe:

  • $24 = 7 \cdot 2 + 5 \cdot 2$
  • $25 = 7 \cdot 0 + 5 \cdot 5$
  • $26 = 7 \cdot 3 + 5 \cdot 1$
  • $27 = 7 \cdot 1 + 5 \cdot 4$
  • $28 = 7 \cdot 4 + 5 \cdot 0$

To argue the inductive step for each case, notice that if the statement is true for some $n=k$, then $k=7x+5y$, which in turn implies $k+5 = 7x + 5(y+1)$. As $n=k+5$ is the next value of $n$ with the same remainder as $k$, the inductive step is established.

Therefore, by the principle of mathematical induction, for $n>23$, there must always exist non-negative integers $x$ and $y$ such that $n=7x+5y$.

QED.