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.

Answer

To show that the square of any positive integer is either of the form \(3m\) or \(3m + 1\) for some integer \(m\), we will use Euclid's division lemma. According to this lemma, for any integer \(a\) and positive integer \(b\), there exist unique integers \(q\) and \(r\) such that:

\[ a = bq + r \]

where \(0 \leq r < b\).

In our case, we will take \(b = 3\). Thus, for any positive integer \(n\), we can write:

\[ n = 3q + r \]

where \(r\) can take values \(0\), \(1\), or \(2\) (since these are the possible remainders when dividing by \(3\)).

### Step 1: Consider the three cases for \(r\)

1. **Case 1:** \(r = 0\)

If \(n = 3q\), then:
\[ n^2 = (3q)^2 = 9q^2 = 3(3q^2) \]
This is of the form \(3m\) where \(m = 3q^2\).

2. **Case 2:** \(r = 1\)

If \(n = 3q + 1\), then:
\[ n^2 = (3q + 1)^2 = 9q^2 + 6q + 1 = 3(3q^2 + 2q) + 1 \]
This is of the form \(3m + 1\) where \(m = 3q^2 + 2q\).

3. **Case 3:** \(r = 2\)

If \(n = 3q + 2\), then:
\[ n^2 = (3q + 2)^2 = 9q^2 + 12q + 4 = 3(3q^2 + 4q + 1) + 1 \]
This is also of the form \(3m + 1\) where \(m = 3q^2 + 4q + 1\).

### Conclusion:

From the three cases, we can conclude that the square of any positive integer \(n\) is either of the form \(3m\) or \(3m + 1\) for some integer \(m\).