Remainders of Large Numbers

[cheiney]

Homework Statement

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

Homework Equations

Congruence Modulo

a$\equiv$b mod n

also

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

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?

 

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

 

[phinds]

The remainder for 1^99 would be 5.

really ?

 

[Mark44]

That's news to me as well.

 

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

 

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

 

[Office_Shredder]

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.

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.

 

[cheiney]

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.

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

 

[Office_Shredder]

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.

 

[cheiney]

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.

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?

 

[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

 

[ehild]

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?

Is it true if a even? For example, 1²+2²+3² divided by 3?

ehild

 

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