# Prove that odd perfect square is congruent to $1$ modulo $8$

How can we prove that every odd perfect square is congruent to $1$ modulo $8$?

-
try some and see what happens. – Will Jagy Dec 31 '12 at 23:47

If $n^2$ is odd, then $n$ must be odd, hence $n=2k+1$. Now, $(2k+1)^2=4k^2+4k+1=4k(k+1)+1$. Since $k$ and $k+1$ are consecutive integers, one of them must be even (that is, it has a factor of $2$), thus $4k(k+1)\equiv0\pmod{8}$. Now it is clear that $n^2\equiv1\pmod{8}$ for all odd integers $n$.

-
Why is 4k(k+1) congruent to 0 (mod 8)? Where is proof that 8 divides 4k(k+1)? – Al Jebr Feb 18 '14 at 5:47
@Student: It is obvious. Clearly, precisely one of $k$ or $k+1$ is even, i.e., $2\mid k(k+1)$, in which case, $8\mid 4k(k+1)$. Amr explains this in his post as well. – Clayton Feb 18 '14 at 19:26

An odd perfect square is of the form $(2k+1)^2$. $$(2k+1)^2=4k^2+4k+1=4(k^2+k)+1$$ Since $k^2+k=k(k+1)$ is always even, $4(k^2+k)$ is always divisible by $8$. Now it follows that every odd square is congruent to $1$ modulo $8$.

In general, for any integers $m,n$ such that $m$ is odd and $n>2$, $m^{2^{n-2}}$ is congruent to $1$ modulo $2^n$. This follows directly from the fact that $U(\mathbb{Z} /2^n\mathbb{Z})\cong \mathbb{Z}_2\oplus \mathbb{Z}_{2^{n-2}}$.

-

Since the square of even and odd integers are even and odd respectively, an odd square must be of the form $(4k\pm 1)^2=16k^2\pm 8k+1=8(2k^2\pm k)+1$ for some integer $k$.

-
If odd squares were $3 \pmod 8,$ would that really be so bad? – Will Jagy Jan 1 '13 at 5:42

Just for fun, I am trying to use 3 instead of 2.

An odd perfect square is of the form $(6k\pm 1)^2$ or$(6k+3)^2$ $= 36k^2\pm 12k+1$ or $36k^2+36k+9$.

$36k^2\pm 12k+1 = 12k(3k\pm 1)+1$. If $k$ is even, $8 | 12k$; if $k$ is odd, $3k\pm 1$ is even, so $8 | 12(3k\pm 1)$.

$36k^2+36k+9 = 36k(k+1)+9$ and $8 | 36k(k+1)+8$ since $k(k+1)$ is even.

Not as simple, but it works.

Probably can be made to work for any odd prime $p$ by looking at $(2pk\pm 1,3,5,...,p)^2$.

-

Observe:

$({\pm 1})^2 \equiv ({\pm 3})^2 \equiv 1 \bmod 8$

-
This is the simplest and best solution presented. – Jonathan Christensen Dec 31 '12 at 23:53
For those who can't quickly prove this on their own, this answer might be the least understandable. – Todd Wilcox Jan 1 '13 at 1:24
What Todd means is that a little explanation would go a long way here. Is this even a real proof, or just proof by example? – Robert Harvey Jan 1 '13 at 1:26
I've been looking at this for about 20 minutes now and trying to figure out how it constitutes a proof, and it must be really good and elegant for it to get the votes it's gotten, but I can't figure it out at all. It seems to be simply saying the first two odd perfect squares are congruent to $1($mod$8)$. That's clearly not a complete proof. What am I missing? More to the point, since I proved this in my head right after reading the question, and I still don't understand this answer, I wonder if the OP will understand this after not being able to prove it another way. – Todd Wilcox Jan 1 '13 at 1:45
@ToddWilcox, all odd numbers are one of $1, -1, 3, -3 \pmod 8.$ Put another way, all odd numbers are $1,3,5,7 \pmod 8,$ as in fact all number are among $0,1,2,3,4,5,6,7 \pmod 8.$ – Will Jagy Jan 1 '13 at 2:10