# euclid division lemma

Let a be any positive integer and b = 3.

Now, a = 3q + r, where q ≥ 0 and 0 ≤ r < 3

Thus, a = 3q or 3q + 1 or 3q + 2.

Therefore, every number can be represented in three forms.

Case 1: when a = 3q.

a3 = (3q)3 = 27q3 = 9(3q3) = 9m; where m is an integer such that m = 3q3.

Case 2: when a = 3q + 1.

a3 = (3q + 1) 3 = 27q3 + 27q2 + 9q + 1 = 9(3q3 + 3q2 + q) + 1 = 9m + 1; where m is an integer such that m = (3q3 + 3q2 + q).

Case 3: when a = 3q + 2.

a3 = (3q + 2) 3 = 27q3 + 54q2 + 36q + 8 = 9(3q3 + 6q2 + 4q) + 8 = 9m + 8; where m is an integer such that m = (3q3 + 6q2 + 4q).

Hence, cube of any positive integer is of the form 9m, 9m + 1 or 9m + 8.

The method or solution starts with the assumption of integer in a form that yield “9”. So, we have chosen like this:

1) numbers that are divisible by 3 can be represented as “3m”.

2) For numbers that are not divisible by 3, two possibilities…

numbers which give 1 as remainder : “3m + 1”

numbers which give 2 as remainder : “3m + 2”

It is 3, so remainder can not exceed 2.

Further you can refer here :