1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: More Proofs: Prove that if n is an odd positive int., then n^2 = 1(mod 8)

  1. Apr 5, 2007 #1
    1. The problem statement, all variables and given/known data

    Prove that if n is an odd positive integer, then [itex]n^2\,\equiv\,1\,\left(mod\,8\right)[/itex].

    2. Relevant equations



    if and only if


    3. The attempt at a solution

    Using the theorem above:



    Then I have this:


    What do I do next to show this for odd positive n?
  2. jcsd
  3. Apr 5, 2007 #2


    User Avatar
    Homework Helper

    This is hardly "beyond calculus". Anyways, you can represent odd numbers with 2k + 1, where k is a natural number (or zero). Then use eg. proof by induction.
  4. Apr 5, 2007 #3


    User Avatar
    Science Advisor
    Homework Helper

    You need to prove that [itex] (2k+1)^2=8p+1 [/itex] for some "k" and "p" in [itex] \mathbb{Z} [/itex].
  5. Apr 5, 2007 #4
    How would I go about proving that?



    Now what?
  6. Apr 5, 2007 #5


    User Avatar
    Homework Helper

    If n is an odd number, then n can be expressed by (2k + 1) where k is any whole number. Right?
    So, we have:
    n2 = (2k + 1)2 = 4k2 + 4k + 1
    = 4 (k2 + k) + 1 = 4k(k + 1) + 1
    What can you say about the product of 2 successive integers? Hint: Is that divisible by 2?
    So, is the product 4k(k + 1) divisible by 8?
    Can you go from here? :)
  7. Apr 5, 2007 #6


    User Avatar
    Homework Helper

    p is any integer, so k^2+k=2p is equivalent to (ie, exactly the same question as) whether k^2+k is even. Well, is it?
  8. Apr 5, 2007 #7
    [itex]k^2\,+\,k[/itex] is always even. If k were odd, adding an odd integer to another odd one produces an even integer. If k were even, then the whole expression is even as well because adding two even integers always results in an even integer.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook