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.

Question

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

Philoid · Accepted Answer

By taking,’ a’ as any positive integer and b = 3.

Applying Euclid’s algorithm

a = 3q + r

Here,

So, a = 3q or 3q+1 or 3q+2

And,

a² = (3q)² or (3q+1)² or (3q+2)²

a² = (9q²) or 9q²+6q+1 or 9q²+12q+4

a² = 3(3q²)² or (3q² + 2q)+1 or 3(3q²+4q+1)+1

a² = 3k₁ or 3k₂+1 or 3k₃+1

Where k₁, k₂ and k₃ are some positive integers

Hence, it can be said that the square of any positive integer is either of the form 3m or 3m+1.