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

. Use Euclid's division lemma to show that the square of any positive

1.	. Use Euclid's division lemma to show that the square of any positive integer is either ofthe form 3m or 3m + 1 for some integer m.
Answer» By Euclid’s division algorithm a = bq + r, where 0 ≤ r ≤ b Put b = 3 a = 3q + r, where 0 ≤ r ≤ 3 If r = 0, then a = 3q If r = 1, then a = 3q + 1 If r = 2, then a = 3q + 2 Now, (3q)^2 = 9q^2 = 3 × 3q^2 = 3m, where m is some integer (3q + 1)^2 = (3q)^2 + 2(3q)(1) + (1)^2 = 9q^2 + 6q + 1 = 3(3q^2 + 2q) + 1 = 3m + 1, where m is some integer (3q + 2)^2 = (3q)^2 + 2(3q)(2) + (2)^2 = 9q^2 + 12q + 4 = 9q^2 + 12q + 4 = 3(3q^2 + 4q + 1) + 1 = 3m + 1, where m is some integer Hence the square of any positive integer is of the form 3m, or 3m +1 But not of the form 3m + 2