Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

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/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search