# How to use the division algorithm to prove these form of integers?

I have in my notes the form of the integers as: Now, I know that I have to use the division algorithim to prove the first form, and I can do this, but in the second form of an integer $4k$ isn't the "so on" redundant by the division alogirithim since there is no integer of the form $x=4k+4$ or does the "so on" simply imply that we can also have $5k, 5k+1....5k+4$ and $6k,6k+1...$?

I have a couple of other questions. I know how to prove the form of the square of any integer, however, in my proof, and any other proof, we assume $k=3q^2+2qr$ and I have also done a similar thing for proving the form of a cube. However, how is this valid since we have assumed the form of every integer to be $3q^2+2qr$, and then not implemented it in the for the form of the square?

• I think the "so on" refers to $5k, 5k+1,\ldots, 5k+4$ [and so on] as you described. – angryavian Jul 13 '15 at 14:51
• Can you use the first form, to show that square must have the form $3k$ or $3k+1$? – John McGee Jul 13 '15 at 14:53
• @JohnMcGee Yes, but I do not see why take a common factor of 3 put during the process. – Reinhild Van Rosenú Jul 13 '15 at 15:02
• I am referring to the accepted answer here math.stackexchange.com/questions/172535/… – Reinhild Van Rosenú Jul 13 '15 at 15:03
• There are integers of the form $4k + 4$. You can rewrite them as $4(k + 1)$, or reset $k$ to $k + 1$ and thus you once again have $4k$. – Bob Happ Jul 13 '15 at 21:19

You have shown that any integer $n$ is of the form $3q+r$ where $r\in \{0,1,2\}$, so its square can be written as $n^2=9q^2+6qr+r^2=3(3q^2+2qr)+r^2$ as you already mentioned. I do not understand your question about "assuming $k=3q^2+2qr$."
The question asks us to show that the remainder of $n^2$ after dividing by $3$ is $0$ or $1$. Since $3(3q^2+2qr)$ is divisible by $3$ it suffices to look at the remainder of $r^2$ when dividing by $3$.
If $r$ is $0$, $1$, or $2$, then $r^2$ is $0$, $1$, or $4$ respectively; so indeed the remainder when dividing by $3$ is $0$ or $1$.
Maybe an example will be clearer. Suppose we want to show that $64$ is of the form $3k$ or $3k+1$. So, $n=8$, and it can be written as $8=2\cdot 3+2$. Then, squaring both sides gives $64 = 4 \cdot 9 + 2 \cdot 2 \cdot 3 + 4 = 3(4 \cdot 3 + 2 \cdot 2) + 4$. What is the remainder when you divide $3(4\cdot 3 + 2 \cdot 2) + 4$ by $3$?
• $4 \equiv 1 (mod\ 3)$, hence either way we get 0 or 1 after dividing by 3. – sarker306 Jul 13 '15 at 15:07
• @ReinhildVanRosenú I've added an example. Perhaps you are confused by the fact that any integer of the form $3k+1$ can also be written in the form $3k+4$... – angryavian Jul 13 '15 at 15:10