# Use the Division Algorithm to show the square of any integer is in the form $3k$ or $3k+1$

Use Division Algorithm to show the square of any int is in the form 3k or 3k+1

What confuses me about this is that I think I am able to show that the square of any integer is in the form $X*k$ where $x$ is any integer. For Example:

$$x = 3q + 0 \\ x = 3q + 1 \\ x = 3q + 2$$

I show $3k$ first $$(3q)^2 = 3(3q^2)$$ where $k=3q^2$ is this valid use of the division algorithm?

If it is then can I also say that int is in the form for example 10*k

for example

$(3q)^2 = 10*(\frac{9}{10}q^2)$

where $k=(\frac{9}{10}q^2)$

Why isn't this valid? Am I using the div algorithm incorrectly to show that any integer is the form 3k and 3k+1, if so how do I use it? Keep in mind I am teaching myself Number Theory and the only help I can get is from you guys in stackexchange.

-
How do you know that $\frac 9 {10}q^2$ is an integer? – azarel Jul 18 '12 at 19:05
Good point I guess that is the reason that is 10k is invalid. The form $(3q+2)^2$ is not in the form 3k or 3k+1 without getting a fraction, how to account for that to finish the problem? – user968102 Jul 18 '12 at 19:15
If $x = 10k$ then you should also consider all the other cases of $x = 10k + 1, 10k+2, \ldots + 10k+9.$ I don't see why you want to consider that. – user2468 Jul 18 '12 at 19:20
$(3q+2)^2$ is not in the form $3k$ or $3k+1$ seemingly. Start expanding the square $(3q+2)^2 = (3q+2)(3q+2) = (3q)^2 + (2)^2 + 2(3q)(2) = ?????$ Can you take it from here? – user2468 Jul 18 '12 at 19:21

By the division algorithm, $$x = 3q + r,\text{ where } r \in \{0, 1, 2\}.$$ So express $$x^2 = 9q^2 + r^2 + 6qr = 3(3q^2 + 2qr) + r^2.$$ For a given $x$ if $r = 0$ or $1,$ then we're done. If $r = 2$ then $r^2 = 4 = 3 + 1,$ and hence $$x^2 = 3\times\text{integer} + 3 + 1 = 3\times(\text{integer} + 1) + 1.$$ We are done.

-
This makes sense to me and I am able to finish problem thank you – user968102 Jul 18 '12 at 19:32

Let $x = 3k+r, r = 0, 1, 2$ by the division algorithm. Squaring $x$, we find $x^2 = 9k^2+6kr+r^2$, or $x^2 = (9k+6r)k+r^2$.

Since $9k+6r$ is divisible by 3 for all integers $k, r$, then we may re-write this as $x^2 = 3k_1 + r^2$.

Using the division algorithm again, we see that $x^2 = 3k_1+r_1, r_1 = 0, 1, 2$. If $r_1 = 2$, then $r = \pm \sqrt{2}$, which is not an integer. Therefore, only $r=0$ and $r=1$ are acceptable.

-

Hint $\$ Below I give an analogous proof for divisor $5$ (vs. $3),$ exploiting reflection symmetry.

Lemma $\$ Every integer $\rm\:n\:$ has form $\rm\: n = 5\,k \pm r,\:$ for $\rm\:r\in\{0,1,2\},\ k\in\Bbb Z.$

Proof $\$ By the Division algorithm

$$\rm\begin{eqnarray} n &=&\:\rm 5\,q + r\ \ \ for\ \ some\ \ q,r\in\Bbb Z,\:\ r\in [0,4] \\ &=&\:\rm 5\,(q\!+\!1)-(5\!-\!r) \end{eqnarray}$$

Since $\rm\:(5\!-\!r)+r = 5,\,$ one summand is $\le 2,\,$ so lies in $\{0,1,2\},\,$ yielding the result.

Theorem $\$ The square of an integer $\rm\,n\,$ has form $\rm\, n^2 = \,5\,k + r\,$ for $\rm\:r\in \{0,1,4\}.$

Proof $\$ By Lemma $\rm\ n^2 = (5k\pm r)^2 = 5\,(5k^2\!\pm 2kr)+r^2\,$ for $\rm\:r\in \{0,1,2\},\,$ so $\rm\: r^2\in\{0,1,4\}.$

Remark $\$ Your divisor of $\,3\,$ is analogous, with $\rm\:r\in \{0,1\}\,$ so $\rm\:r^2\in \{0,1\}.\,$ The same method generalizes for any divisor $\rm\:m,\,$ yielding that $\rm\:n^2 = m\,k + r^2,\,$ for $\rm\:r\in\{0,1,\ldots,\lfloor m/2\rfloor\}.$ The reason we need only square half the remainders is because we have exploited reflection symmetry (negation) to note that remainders $\rm > n$ can be transformed to negatives of remainders $\rm < n,\,$ e.g. $\rm\: 13 = 5\cdot 2 +\color{#0A0} 3 = 5\cdot 3 \color{#C00}{- 2},\,$ i.e. remainder $\rm\:\color{#0A0}3\leadsto\,\color{#C00}{-2},\,$ i.e. $\rm\:3 \equiv -2\pmod 5.\:$ This amounts to using a system of balanced (or signed) remainders $\rm\, 0,\pm1,\pm2,\ldots,\pm n\$ vs. $\rm\ 0,1,2,\ldots,2n[-1].\:$ Often this optimization halves work for problems independent of the sign of the remainder.

All of this is much clearer when expressed in terms of congruences (modular arithmetic), e.g. the key inference above $\rm\:n\equiv r\:\Rightarrow\:n^2\equiv r^2\pmod m\:$ is a special case of the ubiquitous

Congruence Product Rule $\rm\ \ A\equiv a,\ B\equiv b\ \Rightarrow\ AB\equiv ab\ \ (mod\ m)$

Proof $\rm\:\ \ m\: |\: A\!-\!a,\ B\!-\!b\:\ \Rightarrow\:\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ AB - ab$

For an introduction to congruences see any decent textbook on elementary number theory.

-