- Home/
- CDS & Defence/
- Article
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 BYJU'S Exam Prep
Updated on: September 25th, 2023
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
Table of content
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.