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² = (2k + 1)² = 4k² + 4k + 1.

To show that n² ≡ 1 (mod 8), it is sufficient to show that 8|(n² −1).

We have that n² − 1 = 4k² + 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² − 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² = 4(2d + 1)(2d + 2) = 8(2d + 1)(d + 1),

and again, this is divisible by 8.

Thus, in both cases, n² − 1 is divisible by 8,

so n² ≡ 1 (mod 8).