Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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.

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/ 
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/