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
_____________________________________________

If N is Odd


Date: 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/   
    
Associated Topics:
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/