Question

Find the remainder when 100^{100} is divided by 7

Answer 1

Lets try to find a pattern
10/7 remainder is 3
100/7 remainder is 2
1000/7 remainder is 6
It should cycle back to 3 eventually and it will follow the same pattern.
How many zeros will 100^100 have?
Tough problem. I don't know of a faster way.

Answer 2

uhh...200 zeroes?

Answer 3

maybe?

Answer 4

I found the pattern: 3,2,6,4,5,1. So 200/6 and you take the remainder?

Answer 5

Yeah, 200 zeros that's correct
1 zero:3
2 zeros:2
3 zeros:6
4 zeros:rem is 4
5 zeros: rem is 5
6 zeros: rem is 1
7 zeros: rem is back to 3!
So the remainder pattern is 3 2 6 4 5 1 3 2 6 4 5 1 3 2 6 4 5 1......
200 = 28 x 7 +4. So if we carry this pattern out 200 places we'll get the 4th remainder in the cycle ... which is 4.

Answer 6

I thought 200/7 was 33 R 2

Answer 7

200 / 7 = 28.5714 which is 28 rem 4

Answer 8

oops. I did 200 remainder 6

Answer 9

200/6

Answer 10

Since 100 leaves a remainder of 2 when divided by 7, it follows that \(100^{100}\) leaves the same remainder as \(2^{100}\) when divided by 7. Since \(2^3=8\) leaves a remainder of 1 when divided by 7, we note that:\[2^{100}=2^{3(33)+1}=(2^3)^{33}\cdot 2=8^{33}\cdot 1\]which leaves the same remainder as: \[1^{33}\cdot 2=1\cdot 2= 2\]So \(100^{100}\) leaves a remainder of 2 when divisible by 7.

http://www.wolframalpha.com/input/?i=remainder+when+100%5E100+is+divided+by+7

Read about Modular Arithmetic if you want to find out why the above method works.

Answer 11

Take blocks of 3 starting from the right and make every other block is negative (starting with the second block), then sum them. For example: 3,456,989 gives us 989 - 456 + 3 = 536, then 536 mod 7 = 4, our answer to 3,446,989 mod 7.

Using our example \( 100^{100} = 10^{200}\). Fortunately, most of our blocks are zero. The number of zero blocks (of 3) is 200/3 = 66 with the last two digits remaining being 00. The farthest left digit is 1, so we group this with the 00 to get 100. Since this block is the 67th, it will have positive sign: 100 mod 7 = 2, which is our answer to \( 100^{100} \) mod 7. If this had been negative, we would just add 7 to get our answer.