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!

Remainders of Large Numbers

  1. Oct 2, 2013 #1
    1. The problem statement, all variables and given/known data

    (a) Find the remainder when 1^99 + 2^99 + 3^99 + 4^99 + 5^99 is divided by 5.
    (b) Generalize this result


    2. Relevant equations
    Congruence Modulo

    a[itex]\equiv[/itex]b mod n

    also

    a=n*q+b where q is some integer.


    3. The attempt at a solution

    The remainder for 1^99 would be 1.
    The remainder for 5^99 would be 0.

    I'm having difficulty finding the remainder for 2,3,4.

    I'm assuming I have to use modular arithmetic to find the remainder for these, but I'm not sure where to start. Anyone care to point me in the right direction?
     
    Last edited: Oct 2, 2013
  2. jcsd
  3. Oct 2, 2013 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    For ##2^{99}##, note that ##2^4 = 16## which leaves remainder ##1##. So start by using the division algorithm to write ##99 = 4a + b## where ##b < 4##.
     
  4. Oct 2, 2013 #3

    phinds

    User Avatar
    Gold Member
    2016 Award

    really ?
     
  5. Oct 2, 2013 #4

    Mark44

    Staff: Mentor

    That's news to me as well.
     
  6. Oct 2, 2013 #5
    jbunill has offered you an idea, which is a good one. However if you are still not sure how to proceed, try this: compute each of ##2^n## mod 5 where n = 0,1,2, .. 7. Observe what happens. From that point you should be able to compute ##2^{99}## mod 5.
     
  7. Oct 2, 2013 #6
    Thanks everyone for your posts. I figured out the answer to both parts.

    Part a) , the remainder is 0.

    Part b) , If you sum n integers, where n is prime, and divide the sum by n, you will always get a remainder of 0.

    P.S. Phinds and Mark44, I wrote it incorrectly. The remainder should be 1, not 5.

    I especially appreciate brmath's post as this one made the most sense to me.
     
  8. Oct 2, 2013 #7

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This is way too general... according to this claim, if I take 4 and 5, which is two integers, and I sum them, then divide by 2 I get a remainder of zero.
     
  9. Oct 2, 2013 #8
    Ah, I didn't think of that. What if I specify n consecutive integers starting from 1?
     
  10. Oct 2, 2013 #9

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Part (a) is not an example of that though... if it was

    "Find 1+2+3+4+5 mod 5" then it would be, but as written it's not a sum of n consecutive integers.
     
  11. Oct 2, 2013 #10
    Okay I understand what you are saying. What if I said:

    If you sum 1^a+2^a+3^a+...+n^a (where n is a prime number) and divide this sum by n, you end up with a remainder of 0?
     
    Last edited: Oct 2, 2013
  12. Oct 2, 2013 #11

    ehild

    User Avatar
    Homework Helper
    Gold Member

    You can write 4 as -1 mod 5 and 3 as -2 mod 5.

    ( 1 mod5)^99 = (1 mod5)^98 *(1 mod5)
    ( -1 mod5)^99 = (-1 mod5)^98 *(-1 mod5),

    the same with 2 mod5 and -2 mod5.

    How are (k mod5)^98 and (-k mod5)^98 related?

    ehild
     
  13. Oct 2, 2013 #12

    ehild

    User Avatar
    Homework Helper
    Gold Member

    Is it true if a even? For example, 12+22+32 divided by 3?

    ehild
     
  14. Oct 3, 2013 #13
    cheiney What is the connection between amod5 + bmod5 and (a+b)mod5? Figure that out by taking some examples.

    Then figure out ##2^{99}, 3^{99}, 4^{99}## by the method I suggested earlier and use what you just learned about sums and mods.

    It's best not to reach for general answers until you have worked out a number of specific cases.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Remainders of Large Numbers
  1. Large number (Replies: 4)

Loading...