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.

```

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

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search