4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

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

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.