Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
5  
try some and see what happens. –  Will Jagy Dec 31 '12 at 23:47
add comment

5 Answers

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

share|improve this answer
    
Why is 4k(k+1) congruent to 0 (mod 8)? Where is proof that 8 divides 4k(k+1)? –  Lanfranco Feb 18 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 at 19:26
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
If odd squares were $3 \pmod 8,$ would that really be so bad? –  Will Jagy Jan 1 '13 at 5:42
add comment

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

share|improve this answer
add comment

Observe:

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

share|improve this answer
4  
This is the simplest and best solution presented. –  Jonathan Christensen Dec 31 '12 at 23:53
7  
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
2  
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
7  
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
8  
@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
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.