Results 1 to 5 of 5

Math Help - Euclid,s division lemma-please help

  1. #1
    Amy
    Amy is offline
    Junior Member
    Joined
    Feb 2007
    Posts
    59

    Thumbs down Euclid,s division lemma-please help

    Please help me to solve this using Euclid's division lemma

    Show that the cube of any positive integer is of the form 9m,9m+1 or 9m+8.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,911
    Thanks
    775
    Hello, Amy!

    I'm not familiar with Euclid's Division Lemma,
    . . but I have a proof.


    Show that the cube of any positive integer is of the form 9m, 9m+1 or 9m+8.
    We want to show that the cube of any positive integer is: a multiple of 9,
    or one more than a multiple of 9, or eight more than a multiple of 9.


    A positive integer N must be in one of three forms:
    . . . . 3a: . a multiple of three
    . . 3a + 1: one more than a multiple of three
    . . 3a + 2: two more than a multiple of three


    (1) N = 3a
    . . .Then .N .= .(3a) .= .27a .= .9(3a)
    . . .Hence, it is a multiple of 9.

    (2) N = 3a + 1
    . . .Then .N .= .(3a + 1) .= .27a + 27a + 9a + 1 .= .9(3a + 3a + a) + 1
    . . .Hence, it is one more than a multiple of 9.

    (3) N = 3a + 2
    . . .Then .N .= .(3a + 2) .= .27a + 54a + 36a + 8 .= .9(3a + 6a + 4a) + 8
    . . .Hence, it is eight more than a multiple of 9.

    . . Q. E. D.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by Amy View Post
    Please help me to solve this using Euclid's division lemma

    Show that the cube of any positive integer is of the form 9m,9m+1 or 9m+8.
    Euclid's Lemma states that if a prime number p divides a number N (i.e. N is a multiple of p), and N is the product of two numbers a and b, then p must divide at least one of a or b.

    Is this the right lemma? I can't see how to apply it here.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by topsquark View Post
    Euclid's Lemma states that if a prime number p divides a number N (i.e. N is a multiple of p), and N is the product of two numbers a and b, then p must divide at least one of a or b.

    Is this the right lemma? I can't see how to apply it here.

    -Dan
    Yes (did you learn that from me?).

    But, I think he means the division algorithm.
    That is,
    Given: a,b positive integers there exists unique integers q,r such that,
    a=qb+r with 0<=r<b.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Amy
    Amy is offline
    Junior Member
    Joined
    Feb 2007
    Posts
    59
    Thanks every body for the help.
    Now I have a doubt; Euclid's division lemma and division algorithm are different things?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Applying Euclid's Lemma to a problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 8th 2011, 08:05 PM
  2. some confusion on wording of Euclid's Lemma
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 25th 2011, 06:08 PM
  3. Euclid's Lemma Proof by Induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 7th 2011, 02:25 AM
  4. Replies: 0
    Last Post: May 28th 2009, 10:07 AM
  5. Euclid's lemma and induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 26th 2008, 12:44 AM

Search Tags


/mathhelpforum @mathhelpforum