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

By Ritesh|Updated : November 7th, 2022

Using Euclid's division lemma, it is proved that the square of any positive integer is either of form 3m or 3m + 1 for some integer m. Let us assume that ‘a’ is a positive integer:

Consider q as the quotient and r as the reminder, then divide the positive integer a by 3 so that we may deduce from Euclid's Division Lemma that:

a = bq + r {condition for r is (0 ≤ r < b)}

a = 3q + r …… (i) b = 3

Therefore, r is a number that ranges from 0 to 3.

Therefore, r can be either 0, 1 or 2

Case I - When r = 0, the equation (i) becomes

a = 3q

By squaring on both sides,

a2 = 3q2

a2 = 9q2

a2 = 3(3q2)

On simplifying we get

a2 = 3m where 3q2 = m

Case II - When r = 1, the equation (i) becomes

a = 3q + 1

Now, squaring both sides:

a2 = (3q + 1)2

a2 = 3q2 + 12 + 2 (3q) (1)

a2 = 9q2 + 6q + 1

a2 = 3 (3q2 + 2q) + 1

In simplification we get the:

a2 = 3m + 1 where (3q2 + 2q) = m

Case III - When r = 2, the equation (i) becomes

a = 3q + 2

Now, squaring both sides:

a2 = (3q + 2)2

a2 = 3q2 + 22 + 2 (3q) (2)

a2 = 9q2 + 12q + 4

a2 = 3 (3q2 + 4q + 1) + 1

a2 = 3m + 1 where (3q2 + 4q + 1) = m

Therefore, the square of any positive integer is either of form 3m or 3m + 1

Summary:

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

It is demonstrated that the square of every positive integer is either of form 3m or 3m + 1 for some integer m using Euclid's division lemma. To find the HCF of two positive integers a and b we can make use of Euclid’s division algorithm.