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)

Printable View

- Nov 4th 2009, 03:43 PMkashifzaidicongruent 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 PMBruno 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 PMDrexel28
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 PMBruno 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 PMDrexel28
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.

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

We do this by weak induction.**Proof:**

**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 PMBruno J.
Good!

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