Use Euclid’s division lemma to show that the square of any positive integer is either of the form 3m or 3m + 1 for some integer m

Euclid's Division Lemma states that given any two positive integers a and b, there exist unique integers q and r such that a = bq + r, where 0 ≤ r < b.

Let's take a positive integer 'a'. According to Euclid's Division Lemma, we can express 'a' in the form of 3q, 3q+1 or 3q+2 (where q is the quotient).

Now, we need to show that the square of 'a' is either of the form 3m or 3m+1.

Case 1: If 'a' is of the form 3q, then a^2 = (3q)^2 = 9q^2 = 3(3q^2). Here, 3q^2 is an integer, so we can say that a^2 is of the form 3m (where m = 3q^2).

Case 2: If 'a' is of the form 3q+1, then a^2 = (3q+1)^2 = 9q^2 + 6q + 1 = 3(3q^2 + 2q) + 1