# Remainders of Large Numbers

1. Oct 2, 2013

### cheiney

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$\equiv$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. Oct 2, 2013

### jbunniii

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$.

3. Oct 2, 2013

really ?

4. Oct 2, 2013

### Staff: Mentor

That's news to me as well.

5. Oct 2, 2013

### brmath

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.

6. Oct 2, 2013

### cheiney

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.

7. Oct 2, 2013

### Office_Shredder

Staff Emeritus
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.

8. Oct 2, 2013

### cheiney

Ah, I didn't think of that. What if I specify n consecutive integers starting from 1?

9. Oct 2, 2013

### Office_Shredder

Staff Emeritus
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.

10. Oct 2, 2013

### cheiney

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
11. Oct 2, 2013

### ehild

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

12. Oct 2, 2013

### ehild

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

ehild

13. Oct 3, 2013

### brmath

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.