Remainders of Large Numbers

  • Thread starter cheiney
  • Start date
  • #1
11
0

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[itex]\equiv[/itex]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?
 
Last edited:

Answers and Replies

  • #2
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,470
246
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##.
 
  • #5
329
34
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.
 
  • Like
Likes 1 person
  • #6
11
0
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
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,173
330
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.
 
  • #8
11
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.
Ah, I didn't think of that. What if I specify n consecutive integers starting from 1?
 
  • #9
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,173
330
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
11
0
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?
 
Last edited:
  • #11
ehild
Homework Helper
15,543
1,909
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
ehild
Homework Helper
15,543
1,909
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, 12+22+32 divided by 3?

ehild
 
  • #13
329
34
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.
 

Related Threads on Remainders of Large Numbers

Replies
0
Views
2K
  • Last Post
Replies
24
Views
2K
Replies
5
Views
8K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
997
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
4
Views
3K
Replies
9
Views
47K
Replies
5
Views
10K
Top