Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.