How can we prove that every odd perfect square is congruent to $1$ modulo $8$?
Prove that odd perfect square is congruent to $1$ modulo $8$
-
5try some and see what happens. – 2012-12-31
5 Answers
Observe:
$({\pm 1})^2 \equiv ({\pm 3})^2 \equiv 1 \bmod 8 $
-
4This is the simplest and best solution presented. – 2012-12-31
-
9For those who can't quickly prove this on their own, this answer might be the least understandable. – 2013-01-01
-
2What Todd means is that a little explanation would go a long way here. Is this even a real proof, or just proof by example? – 2013-01-01
-
7I'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. – 2013-01-01
-
9@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.$ – 2013-01-01
-
1@ToddWilcox, built into this are observations about ring homomorphisms, such as : if $a \equiv b \pmod m,$ then $a^2 \equiv b^2 \pmod m.$ – 2013-01-01
-
0Oh, cool. I'm glad I asked, and thanks, Will, for clarifying. Upvotes all around! – 2013-01-01
-
1Thanks 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
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$.
-
0If odd squares were $3 \pmod 8,$ would that really be so bad? – 2013-01-01
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$.
-
0Why is 4k(k+1) congruent to 0 (mod 8)? Where is proof that 8 divides 4k(k+1)? – 2014-02-18
-
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
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$.