Odd Numbers and Modulo 8

Date: 09/06/2004 at 04:57:06
From: Guggach
Subject: odd numbers and modulo 8

A friend told me that every odd number >1, multiplied by itsef, modulo
8 always gives 1.  For example, (3*3)%8 == (111*111)%8 == 1.

Is that correct?  If yes, why?  Thanks a lot!

Date: 09/08/2004 at 14:38:43
From: Doctor Beryllium
Subject: Re: odd numbers and modulo 8

Hello Guggach, 

Thanks for writing to Dr Math.  The answer to your first question is
yes; every odd number greater than 1 multiplied by itself is congruent
to 1 modulo 8.

To answer your second question we require a proof.  The following 
should suffice.

Suppose we have an odd number a such that a > 1.  Then,

     a = 2k + 1     where k >= 1

Now a * a is given by:

     a^2 = (2k + 1)(2k + 1) = 4k^2 + 4k + 1

                            = 4(k^2 + k) + 1

So we have,

     a^2 = 4(k^2 + k) + 1        [Equation 1]

We now consider two cases. 

Case 1: k is an even number. In this case we can write k as,

     k = 2n       where n >= 1

We substitute this expression for k into equation 1 and get,

     a^2 = 4((2n)^2 + 2n) + 1

         = 4(4n^2 + 2n) + 1

         = 8(2n^2 + n) + 1

We observe that in case 1 we have,

    a^2 = 8(2n^2 + n) + 1 == 1 mod 8     (== indicates congruence)

Now we investigate case 2: k is odd. In this case we can write k as,

    k = 2n + 1   where n >= 1

We substitute this expression for k into equation 1 and get,

    a^2 = 4((2n+1)^2 + 2n + 1) + 1

        = 4(4n^2 + 4n + 1 + 2n + 1) + 1

        = 4(4n^2 + 6n + 2) + 1

        = 8(2n^2 + 3n + 1) + 1

We observe that in case 2 we have,

    a^2 = 8(2n^2 + 3n + 1) + 1 == 1 mod 8

So the answer to your question of "Why is it so?" would be that:

For any odd integer a > 1,

    a^2 = 8x + 1   where x is a positive integer.

Also there is no special reason to exclude the odd integer 1 since

    1^2 = 1 = 8*(0) + 1 == 1 mod 8

I hope this helps.  If you need further assistance, please write back.

- Doctor Beryllium, The Math Forum
  http://mathforum.org/dr.math/