Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular Arithematic-see if my answer is correct

  1. Jan 25, 2009 #1
    Q- What is the remainder when 1+2+2[tex]^{2}[/tex]+...+2[tex]^{219}[/tex] is divided by 5.

    Solution: 2[tex]^{0}[/tex]=1 mod5
    2[tex]^{1}[/tex]=2 mod5
    2[tex]^{2}[/tex]=4 mod5
    2[tex]^{3}[/tex]=3 mod5
    2[tex]^{4}[/tex]=1 mod5

    Now I take (1,2,4,3) to be a set numbers. Since the summation goes to 219, there are a total of 220/4 = 55 sets. So I add 1+2+4+3= 10 and 10*55 = 550 <- my answer.
     
  2. jcsd
  3. Jan 25, 2009 #2
    Can anyone see if this is correct.
     
  4. Jan 25, 2009 #3

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    No, it has a couple of errors. First, how many residues did you compute (4 or 5)? Or how many congruence classes are there modulo 5?

    Second, can the remainder exceed the divisor?
     
  5. Jan 26, 2009 #4
    i computed 4 residues, the pattern 1,2,3,4 keeps on repeating. you are right about remainder exceeding the divisor. any ideas about how i should compute this?
     
  6. Jan 26, 2009 #5

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Oops, I made a silly mistake. You are correct that the pattern 1,2,4,3 is repeating, since [itex]2^{m+4} \equiv 2^m ~(mod 5)[/itex].

    So you have found out that:

    [tex]\sum_{n=0}^{219}2^n \equiv 550~(mod 5) [/tex]

    What is the least residue of 550 (mod 5)? That is the required answer.

    Now alternatively, you should also be capable of identifying the kind of series that is given to you and evaluating it directly (before looking at congruences).
     
  7. Jan 26, 2009 #6
    so 550 mod 5 is 0, as that leaves no remainder right?
     
  8. Jan 26, 2009 #7

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Correct.

    Have you thought about the more direct approach, by summing the series?
     
  9. Jan 26, 2009 #8
    Geometric series?

    Doesn't that sum to [tex] 2^{220} - 1 [/tex]?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Modular Arithematic-see if my answer is correct
  1. See this (Replies: 8)

  2. Modular arithmetic (Replies: 11)

  3. Modular arithmetic (Replies: 1)

  4. Modular arithmetic (Replies: 4)

  5. Modular Arithmatic (Replies: 6)

Loading...