# 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. Dec 31, 2012 at 23:47

Observe:

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

• This is the simplest and best solution presented. Dec 31, 2012 at 23:53
• For those who can't quickly prove this on their own, this answer might be the least understandable. Jan 1, 2013 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? Jan 1, 2013 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. Jan 1, 2013 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.$ Jan 1, 2013 at 2:10

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? Jan 1, 2013 at 5:42

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$.

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$.

The sum of the first n integers is n(n+1)/2. The product of any two consecutive integers is always even.

Every odd number can be written as the sum of two consecutive integers or (n-1)/2 + (n+1)/2.

The product of these two consecutive numbers is divisible by 2 (which is also the sum of the first (n-1)/2 integers). Therefore, (n2-1)/8 is an integer.

Thus, every odd perfect square is congruent to 1 modulo 8

Consider the group $$(\mathbb{Z}/8\mathbb{Z})^\times = \{, , , \}$$ under multiplication mod 8. Then $$^2 =^2 = ^2 = ^2 \equiv 1 \, \,\mathrm{ mod } \, 8.$$ Since every odd integer is in exactly one of these congruence classes, every odd integer squared is 1 mod 8.