Using Euclid's division lemma to prove that the cube of any positive integer is of the form 9m, 9m+1, or 9m+8

Euclid's division lemma states that for any two positive integers a and b, there exist unique integers q and r such that a = bq + r, where 0 <= r="">< />

Step 1:
Let's consider the cube of any positive integer, say n.
Therefore, n^3 = n x n x n.

Step 2:
Let's divide n by 3 using Euclid's division lemma.
We get, n = 3q + r, where 0 <= r="">< />

Step 3:
Cubing both sides of the equation in step 2, we get:
n^3 = (3q + r)^3
n^3 = 27q^3 + 27q^2r + 9qr^2 + r^3

Step 4:
Now, we need to analyze the possible remainders r^3 can give when divided by 9.

R^3 can give only three possible remainders when divided by 9:
- If r=0, then r^3=0, and the remainder is 0 when divided by 9.
- If r=1, then r^3=1, and the remainder is 1 when divided by 9.
- If r=2, then r^3=8, and the remainder is 8 when divided by 9.

Step 5:
Substituting the possible remainders of r^3 into the equation in step 3, we get:
- When r=0, n^3 = 27q^3, which is of the form 9m.
- When r=1, n^3 = 27q^3 + 27q^2 + 9q + 1, which can be written as 9(3q^3 + 3q^2 + q) + 1, which is of the form 9m+1.
- When r=2, n^3 = 27q^3 + 54q^2 + 36q + 8, which can be written as 9(3q^3 + 6q^2 + 4q) + 8, which is of the form 9m+8.

Conclusion:
Therefore, we have shown that the cube of any positive integer is of the form 9m, 9m+1, or 9m+8, based on the possible remainders when the integer is divided by 3 using Euclid's division lemma.