Question:
Use euclid's division lemma to show that sqaure of any positive integer is of the form 3p,3p 1
Answer:
Let a is any positive integer and b = 3
Since we know by Euclid algorithm, if a and b are two positive integers, there exist unique integers q and r satisfying
a = bq + r where 0 <= r < b
Here b = 3, then
a = 3q + r where 0 <= r < 4
Since 0 <= r < 3, then possible remainder are 0, 1 and 2
Case 1. a = 3q
=> a = 9q2
= 3 * (3q2 )
= 3p {here p = 3q2 }
Case 2. a = 3q + 1
=> a = (3q + 1)2
= 9q2 + 6q + 4
= 3(3q2 + 2q) + 1
= 3m + 1 {here p = 3q2 + 2q}
Case 3. a = 3q + 2
=> a = (3q + 2)2
= 9q2 + 12q + 4
= 9q2 + 12q + 3 + 1
= 3(3q2 + 4q + 1) + 1
= 3m + 1 {here p = 3q2 + 4q + 1}
Hence, from all above cases, it is clear that square of any positive integer is either of the form 3p or 3p + 1
Not what you are looking for? Go ahead and submit the question, we will get back to you.
