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!

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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number Theory with modular arithmetic
Loading...