Show that for any natural number $n>24$ there exist natural numbers $p$ and $q$ such that $ n=5p+7q$

Question

Show that for any natural number n>24 we have :

$n=5p+7q$ such that $p$ and $q$ are natural.

I tried using induction

1) for $n=24$ we have $n=(7 \cdot 2)+(5 \cdot 2)$

2) we suppose that $n=5p+7q$

We prove that :

Show that for any $n>24$, $n+1=5p'+7q'$

If $n$ is even then $p$ and $q$ should be also even ! Same if $n$ is odd ! Then what ?

I think it's not possible to use induction to prove it.

Answer 1

Actually, it is possible using induction. Notice that $1 = 3\times 5 - 2\times 7 = -4\times 5 + 3\times 7$.

So, suppose that $n\ge 24$, with $n = 5p + 7q$ for $p,q\in\mathbb{N}$. Then you just have to show that we can pick $(p,q)$ such that either $$q\ge 2$$ so that we can add $3\times 5 - 2\times 7$ and get $n+1 = 5(p+3) + 7(q-2)$, or that $$p\ge 4$$ so that we can add $-4\times 5 + 3\times 7$ to get $n+1 = 5(p-4) + 7(q+3)$. Now, starting from $24 = 2\times 5 + 7\times 5$, i.e. $(p,q) = (2,2)$, it is possible to successively add either $(3,-2)$ or $(-4,3)$ so that both entries are nonnegative at each step, and I'll leave it to you to figure out exactly how that can happen.

Answer 2

24=7.2+5.2....25=5.5....26=5.1+7.3....27=7.1+5.4....28=4.7....Now if $n>29$ we have $n=5 x+y$ where $y\in \{24,25,26,27,28\}$ and $x\in Z^+$. Since $y=5A+7B$ for some non-negative integers $A,B$, we have $n=5(A+x)+7 B$.