# 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.

• Nonnegative simply means "not negative," so $0$ is nonnegative. – user61527 Nov 20 '13 at 7:55
• – lab bhattacharjee Nov 20 '13 at 8:01

One more solution.

Use the induction.

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

2. 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.

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$.

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$$

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$.

• how to show that $a,b\ge0$ – lab bhattacharjee Nov 20 '13 at 8:02
• oops..sorry.... – Leox Nov 20 '13 at 8:04

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$