# congruent to modulo; the fundamentals

• Nov 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)
• Nov 4th 2009, 03:48 PM
Bruno J.
The odd residue classes modulo 8 are $\displaystyle 1,3,5,7$. Now you just need to check that $\displaystyle 1^2\equiv 3^2\equiv 5^2 \equiv 7^2 \equiv 1 \mod 8$.

(Because every odd integer can be written as $\displaystyle 8k+1,8k+3,8k+5,$ or $\displaystyle 8k+7$.)
• Nov 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 $\displaystyle n=2k+1$ for some $\displaystyle k\in\mathbb{N}$ then $\displaystyle \left(2k+1\right)^2-1=4k^2+4k+1-1=4k(k+1)$. And since either $\displaystyle k$ or $\displaystyle k+1$ is even we see that $\displaystyle 8|4k(k+1)=(2k+1)^2-1=n^2-1$. Therefore $\displaystyle n^2\equiv 1\text{ mod }8$
• Nov 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.
• Nov 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 $\displaystyle n$ is an odd natural number then $\displaystyle n^2\equiv 1\text{ mod }8$

Proof: We do this by weak induction.

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

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

Inductive step- Using the hypothesis we see that $\displaystyle 8|n^2-1$, but the next odd integer is given by $\displaystyle n+2$ and $\displaystyle (n+2)^2-1=n^2+4n+4-1=\left(n^2-1\right)+4(n+1)$. Since $\displaystyle n$ is odd we know that $\displaystyle n+1$ is even therefore $\displaystyle 8|4(n+1)$. So we may conclude that $\displaystyle 8|n^2-1+4(n+1)=(n+2)^2-1\quad\blacksquare$.
• Nov 4th 2009, 05:08 PM
Bruno J.
Good!

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