induction - Prove that every natural number $n>15$ there exist natural numbers $x,ygeqslant1$ which solve the equation.

Prove that every natural number $n>15$ exist Natural numbers $x,y\geqslant1$ which solve the equation $3x+5y=n$.

so i try induction. base case is for $n=16$.

so $\gcd(5,3)=1$, after Euclidean algorithm i found:

$3(32-5t)+5(-16+3t)=16$ so i found that $32-5t>1$c for $x$ and $-16+3t>1$ for $y$ and for $t=6$ $x=2$ and $y=2$ .

now suppose its takes place for $n$.

how i show that for $n+1$?

if there is more elegant way i would love to see.

Answer

For $n=16$, it is easy: $16=2\times3+2\times5$.

Now, let $n\in\mathbb{N}\setminus\{1,2,\ldots,14\}$ and suppose that there are natural numbers $x$ and $y$ such that $n=3x+5y$. Then:

• if $y>1$, $$\begin{align}n+1&=3x+5y+1\\&=3(x+2)+5(y-1)\end{align}$$ and $x+2,y-1\in\mathbb{N}$.


• Otherwise, $n+1=3x+5+1=3x+6$, for some natural number $x$ and so $$n+1=3(x-3)+5\times3.$$ Note the $x-3\in\mathbb N$, since $$\begin{align}n+1\geqslant16&\iff3x+6\geqslant16\\&\iff3x\geqslant10\end{align}$$ and therefore, since $x\in\mathbb N$, $x\geqslant 4$.