Use Euclid's Division Algorithm to show that the cube of any positive integer is either of the 9m, 9m + 1 or 9m + 8 for some integer m

#### Solution

Let **a** and **b** be two positive integers such that **a** is greater than **b**; then:

**a = b**q + r; where q and r are positive integers and 0 ≤ r < b.

Taking b = 3, we get:

a = 3q + r; where 0 ≤ r < 3

⇒ Different values of integer **a** are 3q, 3q + 1 or 3q + 2.

**Cube of 3q** = (3q)^{3} = 27q^{3} = 9(3q^{3}) = 9m; where **m** is some integer.

**Cube of 3q + 1** = (3q + 1)^{3}

= (3q)^{3} + 3(3q)^{2} x 1 + 3(3q) x 1^{2} + 1^{3}

[Q (q + b)^{3} = a^{3} + 3a^{2}b + 3ab^{2} + 1]

= 27q^{3} + 27q^{2} + 9q + 1

= 9(3q^{3} + 3q^{2} + q) + 1

= **9m + 1**; where m is some integer.

**Cube of 3q + 2** = (3q + 2)^{3}

= (3q)^{3} + 3(3q)^{2} x 2 + 3 x 3q x 2^{2} + 2^{3}

= 27q^{3} + 54q^{2} + 36q + 8

= 9(3q^{3} + 6q^{2} + 4q) + 8

= **9m + 8**; where m is some integer.

Cube of any positive integer is of the form 9m or 9m + 1 or 9m + 8.

**Hence the required result.**