Use Euclid Division Lemma to show that the square of any positive integer is either of the form $3q$ or $3q + 1$ for some integer $q$.

Question

Accepted Answer

Step 1: Any positive integer $n$ can be of the form $3m$, $3m + 1$, or $3m + 2$ for some integer $m$.
Step 2: If $n = 3m$: $n^2 = 9m^2 = 3(3m^2) = 3q$, where $q = 3m^2$.
Step 3: If $n = 3m + 1$: $n^2 = 9m^2 + 6m + 1 = 3(3m^2 + 2m) + 1 = 3q + 1$.
Step 4: If $n = 3m + 2$: $n^2 = 9m^2 + 12m + 4 = 3(3m^2 + 4m + 1) + 1 = 3q + 1$. Hence the square of any positive integer is of the form $3q$ or $3q + 1$.

Question

Solution