If N is OddDate: 12/05/97 at 00:44:14 From: waldo Subject: Number theory My question pertains to number theory. I have no idea where to start or which process to use. If you could get me started on the right path then I think I might be able to finish it. The problem is this: Prove that if n is odd, then 8 divides (n^2-1). I know this can be written as a congruence with n^2 congruent to 1 modulus 8, but I am not sure what to do from there. A response of some kind would be greatly appreciated. Thank you for your time! Date: 12/05/97 at 05:09:15 From: Doctor Pete Subject: Re: Number theory Hi, There are a few ways to go about proving this, but they are all essentially the same. Suppose n is odd. Then n = 2k+1 for some integer k. Hence n^2 - 1 = (2k+1)^2 - 1 = 4k^2 + 4k + 1 - 1 = 4k(k+1) But clearly, exactly one of k or k+1 is even; hence n^2 - 1 is divisible by 8. Another way to think about this is to write out squares modulo 8: 0^2 == 0 (mod 8) 1^2 == 1 (mod 8) 2^2 == 4 (mod 8) 3^2 = 9 == 1 (mod 8) 4^2 = 16 == 0 (mod 8) 5^2 = 25 == 1 (mod 8) 6^2 = 36 == 4 (mod 8) 7^2 = 49 == 1 (mod 8) 8^2 == 0^2 == 0 (mod 8) and clearly, we see that the pattern repeats, because x^2 == (x (mod 8))^2 (mod 8). Hence when we look at the odd numbers, they are all 1 (mod 8), or x^2 - 1 == 0 (mod 8). -Doctor Pete, The Math Forum Check out our web site! 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/