Odd Numbers and Modulo 8Date: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/