Results 1 to 3 of 3

Math Help - Every natural number n≥8 can be represented as n=3k+5ℓ

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    1

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

    Hello,
    Can anybody please help me to solve this problem

    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?

    Please, help!
    Thank you in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

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

    Quote Originally Posted by Lissa View Post
    Hello,
    Can anybody please help me to solve this problem

    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?

    Please, help!
    Thank you in advance.
    First show it true for n=8, 9, ..., 15

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

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

    CB
    Last edited by CaptainBlack; October 15th 2011 at 06:33 AM. Reason: reduce the 16 to 15 as in Halls solution
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,413
    Thanks
    1853

    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 2n- 5j\ge 0, -n+ 3j\ge 0. The second gives 3j\ge n, j\ge n/3 and the second 5j\le 2n, j\le 2n/5. And that, of course, will be true if there be at least one integer between 2n/5 and n/3: 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 n\ge 15. You can finish the proof by checking, individually, 8 to 14.
    Last edited by HallsofIvy; October 15th 2011 at 06:43 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove that complex number can represented in this form
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: March 8th 2012, 11:48 PM
  2. Replies: 1
    Last Post: September 29th 2011, 11:26 AM
  3. Replies: 1
    Last Post: January 22nd 2011, 05:14 AM
  4. Every natural number is sum of powers of 2
    Posted in the Number Theory Forum
    Replies: 23
    Last Post: January 13th 2010, 11:58 PM
  5. Prove natural number
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 25th 2009, 10:55 AM

Search Tags


/mathhelpforum @mathhelpforum