Question

Use Euclid’s Division Algorithm to show that the squares of following numbers is either of form 3m or 3m + 1 for some integer m.

253

Answer 1

Euclid’s Division Algorithm: For any two positive integers a and b, $a=bq+r,0\le r<b$

Assume:

Let a be any positive integer and b = 3.

Then a = 3q + r for some integer q ≥ 0

And r = 0, 1, 2 because 0 ≤ r < 3

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

Case 1: a = 3q

$\begin{array}{rcl}{a}^2& =& {\left(3q\right)}^2\\ & =& 9q^2\\ & =& 3\times 3q^2\\ & =& 3m,\mathrm{where}m=3q^2\end{array}$

Case 2: a = 3q + 1

$\begin{array}{rcl}{a}^2& =& {\left(3q+1\right)}^2\\ & =& 9q^2+6q+1\\ & =& 3\times \left(3q^2+2q\right)+1\\ & =& 3m+1,\mathrm{where}m=3q^2+2q\end{array}$

Case 3: a = 3q + 2

$\begin{array}{rcl}{a}^2& =& {\left(3q+2\right)}^2\\ & =& 9q^2+12q+4\\ & =& 3\times \left(3q^2+4q+1\right)+1\\ & =& 3m+1,\mathrm{where}m=3q^2+4q+1\end{array}$

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