# Thread: Every natural number n≥8 can be represented as n=3k+5ℓ

1. ## Every natural number n≥8 can be represented as n=3k+5ℓ

Hello,

Every natural number n≥8 can be represented as n=3k+5ℓ, k,l are
natural numbers.

so, that true for n=8,9,10 - we can easily check it. Should I use
prove by induction? Then , how?
Or, is there's any other way?

2. ## Re: Every natural number n≥8 can be represented as n=3k+5ℓ

Originally Posted by Lissa
Hello,

Every natural number n≥8 can be represented as n=3k+5ℓ, k,l are
natural numbers.

so, that true for n=8,9,10 - we can easily check it. Should I use
prove by induction? Then , how?
Or, is there's any other way?

First show it true for $\displaystyle n=8, 9, ..., 15$

Now suppose it true for some $\displaystyle k_0 \ge 15$ , that for all $\displaystyle 8 \le k \le k_0$ that $\displaystyle k$ may be written in the required form, then proceed by strong induction...

Hint: split $\displaystyle k_0+1$ into the sum of two integers between $\displaystyle 8$ and $\displaystyle k_0$

CB

3. ## Re: Every natural number n≥8 can be represented as n=3k+5ℓ

A proof that does not involve induction:

This is, basically, trying to solve the Diophantine equation 3k+ 5l= n. 3 divides into 5 once with remainder 2: 5- 3= 2. 2 divides into 3 once with remainder 1: 3- 2= 1. If we replace the "2" in that second equation with 5- 3 we get 3- (5- 3)= 2(3)+ (-1)(5)= 1. Now multiply the entire equation by n to get (2n)(3)+ (-n)(5)= n (which simply says 6n- 5n= n). One solution to the equation 3k+ 5l= n is k= 2n, l= -n. But it is clear that adding any multiple of -5 to k and any multiple of 3 to l will give the same thing: if k= 2n- 5j and l= -n+ 3j, 3(2n- 5j)+ 5(-n+ 3j)= 6n- 5n- 15j+ 15j= n.

So the problem becomes, can we choose j so that both k and l are natural numbers (meaning non-negative integers here)? That will be true if $\displaystyle 2n- 5j\ge 0$, $\displaystyle -n+ 3j\ge 0$. The second gives $\displaystyle 3j\ge n$, $\displaystyle j\ge n/3$ and the second $\displaystyle 5j\le 2n$, $\displaystyle j\le 2n/5$. And that, of course, will be true if there be at least one integer between 2n/5 and n/3: $\displaystyle 2n/5- n/3= n(2/5- 1/3)= n((6- 5)/15)= n(1/15)\ge 1$.

That shows that this can be done for $\displaystyle n\ge 15$. You can finish the proof by checking, individually, 8 to 14.