Prove that for $n\ge 8$ there are nonnegative integers x and y s.t $3x+5y=n$ 
Prove that for every integer $n\ge 8$ there are nonnegative integers $x$ and $y$ such that $3x+5y=n$ 

Attempt: First of all I want to make it clear whether zero is a nonnegative integer. It should be since it is necessary for the statement to work. Second, I am not sure what method to use. Will proof by cases work? I will have four cases: x is even y is even, x is even y is odd, x is odd y is even, x is odd y is odd. I am not sure how to show that it will cover all integers greater than eight. Thank you for your help.
 A: HINT:
$$3m=3\cdot m+5\cdot0\text{ for }m\ge0$$
$$3m+8=3\cdot (m+1)+5\cdot1\text{ for }m\ge-1$$
$$3m+7=3(m-1)+5\cdot2\text{ for }m\ge1$$
A: The numbers $3$ and $5$ are realively primes therefore there exists (by Euclid algorithm)  $a,b$ such that $3 a+5 b=1.$ It impliles that $3 an+5 bn=n.$ Now put $x=a n$ and $y= b n.$
Easy to see that $a=2$ and $b=-1$. Thus $x=2n$ $y=-n$.
A: Here is a boring way:
If $3x+5y = n$, then $x(3+1)+5(y+1) = n+8$. Hence I only need to show it for $n=8,...15$.
This we get from $8=3+5$, $9=3\cdot 3$, $10=2 \cdot 5$, $11=2 \cdot 3 + 5$, $12=4\cdot 3$, $13 = 3+2 \cdot 5$,
$14 = 3 \cdot 3+5$,
$15 = 5 \cdot 3$.
A: One more solution.
Use the induction.


*

*Check  that the statement is true for $n=8,9,\ldots,16.$

*Suppose we already prove it for all numbers less than  $n$, $n>16.$ Since $n>16$ then we can write $n=n_1+n_2$ where $n_1,n_2 >8.$ By induction assumption we may write $3x_1+5y_1=n_1$, $3x_2+5y_2=n_2$ for some $x_1,x_2,y_1,y_2 \geq 0.$ Therefore $n=n_1+n_2=3(x_1+x_2)+5(y_1+y_2)$  and $x_1+x_2 \geq 0,$ and $y_1+y_2 \geq 0$ as required.
A: Here is perhaps a more intuitive method/approach using strong induction that requires less work in the base case.
$Proof.$ We will prove that $\forall n\in\mathbb{Z} \ge 8$ there exists an $x,y \in \mathbb{Z^+}$ such that $3x+5y=n$.
Base Case. We will show that our proposition holds for $n=8,9,10,11,12$. Observe that $8=3(1)+5(1)$, $9=3(3)+5(0)$, $10=3(0)+5(2)$, $11=3(2)+5(1)$, and $12=3(4)+5(0)$. Thus our proposition holds for $n=8,9,10,11,12$.
Inductive Step. Assume $12\le i \le k$ and $k \ge 12$ and that $3x+5y = i$ where $x$ and $y$ are positive integers. 
Then $$\begin{align}k+1 &= 5 + (k-4) \\
&= 5 + 3x + 5y \qquad\text{(by inductive hypothesis)}\\
&=5(y+1)+3x.\end{align}$$
It follows by mathematical induction that $\forall n\in\mathbb{Z} \ge 8$ there exists an $x,y \in \mathbb{Z^+}$ such that $3x+5y=n$. $\Box$ 
