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

#1 RedPhoenix   User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 10-November 09

Induction proof - Discrete Structures

Post icon  Posted 13 November 2009 - 10:39 AM

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!

Is This A Good Question/Topic? 0
  • +

Replies To: Induction proof - Discrete Structures

#2 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

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 :)

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

Was This Post Helpful? 1
  • +
  • -

#3 RedPhoenix   User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 10-November 09

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.
Was This Post Helpful? 0
  • +
  • -

#4 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Induction proof - Discrete Structures

Posted 13 November 2009 - 11:00 PM

no problem, glad i could help..sorry that it looks messy
Was This Post Helpful? 0
  • +
  • -

#5 RedPhoenix   User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 10-November 09

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!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1