# congruent to modulo; the fundamentals

• November 4th 2009, 03:43 PM
kashifzaidi
congruent to modulo; the fundamentals
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)
• November 4th 2009, 03:48 PM
Bruno J.
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$.)
• November 4th 2009, 04:07 PM
Drexel28
Quote:

Originally Posted by kashifzaidi
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$
• November 4th 2009, 04:42 PM
Bruno J.
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.
• November 4th 2009, 04:53 PM
Drexel28
Quote:

Originally Posted by Bruno J.
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$.
• November 4th 2009, 05:08 PM
Bruno J.
Good!

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