# Prove that if n is an odd positive integer, then n^2 ≡ 1 (mod 8).

## Solution

If n is odd, we can write n = 2k + 1 for some integer k.

Then n^{2} = (2k + 1)^{2} = 4k^{2} + 4k + 1.

To show that n^{2} ≡ 1 (mod 8), it is sufficient to show that 8|(n^{2} −1).

We have that n^{2} − 1 = 4k^{2} + 4k = 4k(k + 1).

Now, we have two cases to consider:

if k is even, there is some integer d such that k = 2d.

Then n^{2} − 1 = 4(2d)(2d+1) = 8d(d+1),

Clearly, this is divisible by 8 since it is a multiple of 8.

If k is odd, then there is some integer d such that k = 2d + 1.

Then n^{2} = 4(2d + 1)(2d + 2) = 8(2d + 1)(d + 1),

and again, this is divisible by 8.

Thus, in both cases, n^{2} − 1 is divisible by 8,

so n^{2} ≡ 1 (mod 8).