3
$\begingroup$

Prove that there exists $i, j \in \mathbb{N}$ such that $n=3i+5j$ for $n\ge 8$

I'm having a hard time with this exercise, I'm trying to prove it by induction:

Basis step:

  • $n=8 \implies 8=3\cdot1+5\cdot 1$

  • $n=9 \implies 9=3\cdot3+5\cdot0$

  • $n=10 \implies 10=3\cdot0+5\cdot2$

Induction step:

If it's true for $n=h$ then it must be true for $n=h+1$.

So now, I don't know how to begin proving that $k+1=3i+5j$.

5 Answers 5

4

Hint: Go from $n$ to $n+3$, that is easyer since you have base for $8$, $9$ and $10$:

If $$n=3a+5b$$ then $$n+3 = 3(a+1)+5b$$

0

Hint $:$ $3$ and $5$ are relatively prime to each other.

0

Take any $n>7$. Set $j = floor(n/5)$. if $3|n-5j$ then we are done.
Note than exactly one of $x,x+5,x+10$ is divisible by 3 if $x\in \mathbb N$
Now, if $n = 8,9,10$, we know the solution. if $n>10$ then current $j\ge2$ so consider $n-5j+5$ and $n-5j+10$.
say $3|n-5j+10$. then set $j = floor(n/5)-2$ and you're done
say $3|n-5j+5$ . then set $j= floor(n/5)-1$ and you're done

0

Assuming you mean $i,j\in\mathbb{Z}$ we can easily show that we can write $1=3i+5j$ for some $i,j\in\mathbb{Z}$.

Indeed, choose $i=-3$ and $j=2$. Suppose we get an integer $n$ then we know $n=1\cdot n=(-3\cdot 3+2\cdot 5) n= 3(-3n)+5(2n)$.

So we can simply choose $i=-3n$ and $j=2n$.

0

Trick is induction step doesn't need to be base case $n = 8$ and the induction step from $k\to k+1$.

You can have base cases $n=8,9,10$ and induction step from $k \to k+3$. So the base case $n=8$ will give you $k=8,11,14,17.....$ and the base case $n=9$ will give you $k=9,12,15,18,....$ and base case $n=10$ will give you $k =10,13,16,19,.....$ and between the three base cases and the ability to induct from one case to the case three steps up... that's enough to conclude it's true for all.

Now to figure out the induction step: if $k = 3i + 5j$ then we can find $k+3 = ......$ Well, that's just too easy, isn't it?

.... alternative....

$1 = 2*3 - 1*5$ and $1 = 2*5 - 3*3$.

So if $k = 3*i + 5*j$ then $k+ 1 = 3(i+2) + 5(j-1)$ or $k+1 = 3(i-3) + 5(j+2)$.

If $j \ge 1$ we can do $k+1 = 3(i+2) + 5(j-1)$. If $i\ge 3$ we can do $k+1 =3(i-3) + 5(j+2)$.

So we can always go from $k\to k+1$ so long as either $j \ge 1$ or $i \ge 3$.

But what if $j \le 0$ and $i\le 2$? Well, then $n\le 3*2 + 5*0 = 6$. Which is not an issue if our base cases are $n = 8,9,10$.