congruent to modulo; the fundamentals

kashifzaidi · #1 $Old$ November 4th, 2009, 05:43 PM

Show that if n is an odd positive integer, then
_
n^2 is congruent to 1 modulo 8, i.e., n^2 = 1(mod 8)

Bruno J. · #2 $Old$ November 4th, 2009, 05:48 PM

The odd residue classes modulo 8 are $1,3,5,7$ . Now you just need to check that $1^2\equiv 3^2\equiv 5^2 \equiv 7^2 \equiv 1 \mod 8$ .

(Because every odd integer can be written as $8k+1,8k+3,8k+5,$ or $8k+7$ .)

Drexel28 · #3 $Old$ November 4th, 2009, 06:07 PM

Quote:

Originally Posted by kashifzaidi $View Post$

Show that if n is an odd positive integer, then
_
n^2 is congruent to 1 modulo 8, i.e., n^2 = 1(mod 8)

Alternatively, we know $n=2k+1$ for some $k\in\mathbb{N}$ then $\left(2k+1\right)^2-1=4k^2+4k+1-1=4k(k+1)$ . And since either $k$ or $k+1$ is even we see that $8|4k(k+1)=(2k+1)^2-1=n^2-1$ . Therefore $n^2\equiv 1\text{ mod }8$

Bruno J. · #4 $Old$ November 4th, 2009, 06:42 PM

This is good; it has the advantage of not relying on (general) principles of modular arithmetic. However, you would have a bit more trouble generalizing this type of argument; for instance proving that the square of every integer relatively prime to 12 is congruent to 1 modulo 12 might make the argument quite a lot less elegant.

Drexel28 · #5 $Old$ November 4th, 2009, 06:53 PM

Quote:

Originally Posted by Bruno J. $View Post$

This is good; it has the advantage of not relying on (general) principles of modular arithmetic. However, you would have a bit more trouble generalizing this type of argument; for instance proving that the square of every odd integer is congruent to 1 modulo 12 might make the argument quite a lot less elegant.

I agree this method lacks generality. But when questions are posed in such a way that the numbers "work out nice" I assume that is how it should be done.

Also, this question lends itself to induction.

Problem: Prove that if $n$ is an odd natural number then $n^2\equiv 1\text{ mod }8$

Proof: We do this by weak induction.

Base case- Trivially $1^2=1\equiv 1\text{ mod }8$

Inductive hypothesis- Assume that $n^2\equiv 1\text{ mod }8$

Inductive step- Using the hypothesis we see that $8|n^2-1$ , but the next odd integer is given by $n+2$ and $(n+2)^2-1=n^2+4n+4-1=\left(n^2-1\right)+4(n+1)$ . Since $n$ is odd we know that $n+1$ is even therefore $8|4(n+1)$ . So we may conclude that $8|n^2-1+4(n+1)=(n+2)^2-1\quad\blacksquare$ .

Bruno J. · #6 $Old$ November 4th, 2009, 07:08 PM

Good!

Fixed a mistake in my post. "Odd" is not what I meant!