Question

What's the remainder when you divide 16^103 by 11?

Answer 1

just do 16^103 on your scientific calculator and then divide the number by 11

Answer 2

Error...

Answer 3

1.458824

Answer 4

Nope

Answer 5

The remainder must be an integer.

Answer 6

less than 11

Answer 7

I'm really rusty with my number theory, but I think this is how you do it:
16^103=(16^)(16^5)(16^2)(16^1)(16^0).

I'm going to use = for "congruent"
16^0=1mod11
16^1=5mod11
16^2=5^2mod11=3mod11
16^5=3^3mod11=5mod11
16^6=5^2mod11=3mod11

So you get 16^103=1*5*3*5*3=5mod11

I may have made a mistake in there, but I think the steps are correct. It's called successive squaring.

Answer 8

Right idea, wrong answer:--it's 4

Answer 9

Shoot, where did I mess up?

Answer 10

Not sure, I went a different way, do you want to see it?

Answer 11

Sure!

Answer 12

Oh, I see what I did wrong. I messed up on the powers of 5 and 3

Answer 13

16 = 5^103 = (5^10)^10 * 5^3 = 125 = 4 (all mod11)

Answer 14

Ah, we used the same method, but you were smarter about it.

Answer 15

Yes, u have flt a^p-1 = 1 (mod p)

Answer 16

I always forget about Fermat...

Answer 17

He'd be terribly upset to hear that...:-)

Answer 18

At least I'm not confined to writing in the margin

Answer 19

I had Goldbach on a serviette, the waiter took it away....

Answer 20

Haha, nice

Answer 21

Lemme try this again:
16^103=(16^64)(16^32)(16^4)(16^2)(16^1)
*16^1=5mod11
*16^2=3mod11
*16^4=9mod11
16^8=4mod11
16^16=5mod11
*16^32=3mod11
*16^64=9mod11

16^103=5*3*9*3*9=3645=4mod11
Much better. Maybe I should have consulted a book before I wrote anything...

Answer 22

Since we know 16^10 is congruent to 1 mod 11, we should use the division algorithm on 103 to get:
\[16^{103} = 16^{10(10)+3} = (16^{10})^{10}(16^{3}) \equiv (1^{10})(16^{3}) \equiv 16^{3}\]
but 16 is congruent to 5 mod 11, so we have:
\[16^{3} \equiv 5^{3} \equiv 125 \equiv 4 \mod 11\]