Thread: Euclid,s division lemma-please help

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.

Originally Posted by Amy

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

Originally Posted by topsquark

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.

Thanks every body for the help.
Now I have a doubt; Euclid's division lemma and division algorithm are different things?