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, 04: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, 04:48 PMBruno J.
The odd residue classes modulo 8 are . Now you just need to check that .

(Because every odd integer can be written as or .) - Nov 4th 2009, 05:07 PMDrexel28
- Nov 4th 2009, 05: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, 05: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 is an odd natural number then**Problem:**

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

**Base case**- Trivially

**Inductive hypothesis**- Assume that

**Inductive step**- Using the hypothesis we see that , but the next odd integer is given by and . Since is odd we know that is even therefore . So we may conclude that . - Nov 4th 2009, 06:08 PMBruno J.
Good!

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