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

Nov. 28, 2020

Archangel Macsika Sikademy Image

Archangel Macsika

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

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

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

and again, this is divisible by 8.

Thus, in both cases, n2 − 1 is divisible by 8,

so n2 ≡ 1 (mod 8).

If you would like to see a different solution or an implementation in a different programming language Kindly let us know



Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers