Hey all, I'm taking discrete structures right now and I'm still trying to get the hang of proofs. I'm having a little trouble with this one:

Prove that if n is an odd positive integer, then n^2 mod8 = 1mod 8.

I figured induction might work for this one so that's the direction I took.

so I know that n can be written as 2k+1 for some k>=0 because it's odd

The base case is obvious:k=0 so n=1, so 1mod8 = 1mod8

my inductive hypothesis:

for some k>0

(2k+1)^2 mod8=1 mod8

but i'm having trouble with my inductive step. i just can't find a way to manipulate my hypothesis to get a (2*(k+1) +1)^2 mod8=1 mod8.

Any help would be appreciated. Thanks!

## 4 Replies - 4791 Views - Last Post: 14 November 2009 - 11:21 AM

##
**Replies To:** Induction proof - Discrete Structures

### #2

## Re: Induction proof - Discrete Structures

Posted 13 November 2009 - 10:45 PM

i dont really see the induction in it, sure you can do it but it may not be the easiest way, atleast not for me..

i thought of it this way

since n is odd then also n^2 is odd(proof of this lemma should be easy)

n^2 will always be larger than 8 for every positive odd integer > 1

for the case of n^2 = 1, 1mod8 = 1

now since n^2 can be written as 2k+1 for some positive integer k and n^2 > 8

(2k+1)mod 8 = 2k mod 8 + 1 mod 8

since 2k is even and >= 8 then the result will be 0, and 1 mod 8 is 1

therefore the overall result will be 1

this is my informal sketch of this proof..it may be a little messy and it may contain holes but i am sort of rusty with proofs myself and still working on it, anyway hope this helps

i thought of it this way

since n is odd then also n^2 is odd(proof of this lemma should be easy)

n^2 will always be larger than 8 for every positive odd integer > 1

for the case of n^2 = 1, 1mod8 = 1

now since n^2 can be written as 2k+1 for some positive integer k and n^2 > 8

(2k+1)mod 8 = 2k mod 8 + 1 mod 8

since 2k is even and >= 8 then the result will be 0, and 1 mod 8 is 1

therefore the overall result will be 1

this is my informal sketch of this proof..it may be a little messy and it may contain holes but i am sort of rusty with proofs myself and still working on it, anyway hope this helps

This post has been edited by **mostyfriedman**: 13 November 2009 - 10:52 PM

### #3

## Re: Induction proof - Discrete Structures

Posted 13 November 2009 - 10:56 PM

That actually makes a lot more sense than what I was trying to do. Thanks a lot! That should get me going.

### #4

## Re: Induction proof - Discrete Structures

Posted 13 November 2009 - 11:00 PM

no problem, glad i could help..sorry that it looks messy

### #5

## Re: Induction proof - Discrete Structures

Posted 14 November 2009 - 11:21 AM

Here's the way I ended up proving it for those that care (not inductively like mostyfriedman said) :

n=2k+1 for some k>=0. thus n^2=4k(k+1) +1.

either k or k+1 is even so

n^2=8x+1 for some x

so n^2mod8= (8x+1)mod8 = (8x mod8 + 1mod8)mod8

=(0+1)mod8 = 1mod8 which is what I was after. Thanks for the help!

n=2k+1 for some k>=0. thus n^2=4k(k+1) +1.

either k or k+1 is even so

n^2=8x+1 for some x

so n^2mod8= (8x+1)mod8 = (8x mod8 + 1mod8)mod8

=(0+1)mod8 = 1mod8 which is what I was after. Thanks for the help!

Page 1 of 1