14
$\begingroup$

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

  • 5
    try some and see what happens.2012-12-31

5 Answers 5

35

Observe:

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

  • 1
    Thanks Jonathan. :) Todd, I apologize if it was not clear. I meant it as a hint. When I posted the answer, two other answers had already outlined an algebraic way of doing it. I think modular arithmetic is really cool for proving questions like this. So I wanted to give a different perspective.2013-01-01
34

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

15

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

  • 0
    If odd squares were $3 \pmod 8,$ would that really be so bad?2013-01-01
12

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

  • 0
    @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.2014-02-18
2

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