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.
Best 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: