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: Number Theory with modular arithmetic

  1. Sep 21, 2010 #1
    1. The problem statement, all variables and given/known data
    When a is odd, show [tex]\frac{a^2-1}{8}[/tex] is an integer. Then prove by induction [tex]n \geq 2[/tex] that for all odd numbers [tex]a_1,a_2,...,a_n,[/tex]

    [tex]
    \frac{(a_1a_2...a_n)^2 - 1}{8} \equiv \frac{a^2_1 - 1}{8} + \frac{a^2_2 - 1}{8} + ... + \frac{a^2_n - 1}{8} \ mod \ 2
    [/tex]


    2. Relevant equations



    3. The attempt at a solution
    I proved that [tex]\frac{a^2-1}{8}[/tex] is an integer for odd a without much difficulty, but I am having trouble even proving the base case, n=2 for this.

    From a previous problem, I already proved [tex]\frac{(a_1a_2...a_n) - 1}{2} \equiv \frac{a_1 - 1}{2} + \frac{a_2 - 1}{2} + ... + \frac{a_n - 1}{2} \ mod \ 2[/tex] for odd a. So I thought I might be able to use that and separate it into [tex]\frac{(a_1a_2...a_n) - 1}{2}[/tex] and [tex]\frac{(a_1a_2...a_n) + 1}{4}[/tex] but that didn't get me anywhere. I also tried representing the a's as 2k+1 for an integer k. But I just can't get anywhere.

    Also, I figure that if I can prove that the left and right hand sides are both odd or both even, then I am done.
     
  2. jcsd
  3. Sep 21, 2010 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Isn't

    [tex]

    \frac{(a_1a_2...a_n)^2 - 1}{8} \equiv \frac{a^2_1 - 1}{8} + \frac{a^2_2 - 1}{8} + ... + \frac{a^2_n - 1}{8} \ mod \ 2

    [/tex]

    already in the form

    [tex]
    \frac{(b_1b_2...b_m) - 1}{2} \equiv \frac{b_1 - 1}{2} + \frac{b_2 - 1}{2} + ... + \frac{b_m - 1}{2} \ mod \ 2
    [/tex]

    ? (where I have changed the variable names to help reduce the risk of you confusing yourself)
     
  4. Sep 21, 2010 #3
    Ok, I got it, thanks
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook