Prove that the square of any odd number is equal to a multiple of $8$ plus $1$

Question

Given the following problem:

Prove that the square any odd number is equal to a multiple of $8$ plus $1$:

1. Using congruence.
2. Applying the division algorithm.

I believe that the square of an odd number would be represented by $(2k_1-1)^2$ and based on the problem, it appears to be stating that; $(8k_2+1)$ divides $(2k_1-1)^2$.

Therefore, for the first part of the problem (1.), would it be $(2k_1-1)^2\equiv0\mod{(8k_2+1)}$?

If not how can I interpret and solve this problem including the second part?

Answer 1

Let $k$ be a non-negative integer. Then $$(2k+1)^2=4k^2+4k+1=4k(k+1)+1.$$ The product of two consecutive integers must be even so let $k(k+1)=2n$ for some $n\in\mathbb{N}$. Then $$(2k+1)^2=4(2n)+1=8n+1\equiv1 \mod8$$ as desired.

Answer 2

$$(2n+1)^2 =4n^2+4n+1=4n(n+1)+1.$$ Notice that one of $n$ or $n+1$ is even, so $n(n+1)$ is always even. That makes $4n(n+1)$ a multiple of 8.Thus $(2n+1)^2=8k+1$ That is $(2n+1)^2\equiv 1$ mod(8).

Answer 3

You are correct that any odd number can be represented as $2k_{1}-1$ for some integer $k$. You want to interpret the problem as saying that $$(2k-1)^{2} = 8k_{2} +1$$ for some integer $k_{2}$, or $$(2k-1)^{2} \equiv 1 \bmod{8}$$ (not that it is divisible by $8k_{2}+1$). Another way of saying this is that when you divide $(2k-1)^{2}$ by $8$, you have a remainder of $1$.

Answer 4

Here is a very easy way, which should be better known:

Every odd number is of the form $4n\pm 1$ and $$(4n\pm 1)^2=16n^2\pm 8n +1$$

---

Here is another way just for the record. The squares of consecutive odd numbers differ by a multiple of $8$ because $$(2n+1)^2-(2n-1)^2=8n$$ Since $1^2=1$ leaves remainder $1$ when divided by $8$, this is true for any odd number.

Note also that you can write $(2n+1)^2=8T_n+1$ where $T_n$ is the $n^{th}$ triangular number. There is a neat dissection of an odd square into triangles plus the central square which gives a visual demonstration.

Answer 5

Use induction to show $(2n+1)^2 \equiv 1 \mod 8$.

When $n=0$, $1 \equiv 1 \mod 8$.

Assuming it is true for $n=k$, we'll prove for $n=k+1$: $$(2(k+1)+1)^2=((2k+1)+2)^2=(2k+1)^2+4(2k+1)+4=(2k+1)^2+8(k+1) \equiv (2k+1)^2 \equiv 1 \mod 8.$$

Answer 6

The usual proof for such a congruence questions goes like this:

If $n$ is odd, then $n \equiv 1,3,5,7 \bmod 8$.

If $n \equiv 1 \bmod 8$, then $n^2 \equiv 1 \bmod 8 \equiv 1 \bmod 8$.

If $n \equiv 3 \bmod 8$, then $n^2 \equiv 9 \bmod 8 \equiv 1 \bmod 8$.

If $n \equiv 5 \bmod 8$, then $n^2 \equiv 25 \bmod 8 \equiv 1 \bmod 8$.

If $n \equiv 7 \bmod 8$, then $n^2 \equiv 49 \bmod 8 \equiv 1 \bmod 8$.