Simple Algebra question about division/prime factorizations

[missavvy]

Homework Statement

Find the remainder of the division of 7^211 by 11

The Attempt at a Solution

I know this is an extremely trivial question, but I just don't understand what to do.
I've searched my textbook for an example, and I could of sworn I had one in my notes, but I really don't know how to do this! :S
7^211 = 11q + r, right?

but then what? or do i write the prime factorizations of 211... of 7? of 11?

if anyone can just help me with the method, or redirect me to a website with great notes.. :)

 

[VeeEight]

Use Fermat's Little Theorem, work modulo 11, and write 211 as 11x+y, for some integers x, y.

 

[Gib Z]

Have you learned modular arithmetic? If you haven't, its basically something that allows you to throw away the parts of a number with a factor and leave you with a remainder. But since you don't know about it I'll explain it this way:

I can split up the exponent in $7^{211}$ for eg like this $7^2 X 7^{209}= 49 X 7^{209}$. Now 49 is an easy number to deal with, and we see that 11 goes into it 4 times, and that 49 = 4(11) + 5. So now we can expland the original thing;

$$7^{211} = 7^2 x 7^{209} = (44 + 5) 7^{209} = 44X 7^{209} + 5X7^{209}$$

Now, since we are only interested in the remainder when divided by 11, rather than how many times exactly, we any drop off any multiplies of 11 we see, and we just created one, namely the 44* 7^(209) term.

So the remainder of 7^(211) is the same as the remainder of 5 x 7^(209). In effect, you can just broken it down, and the answer can be achieved by continuing until you reach a number less than 11, but it will be long if you just keep taking off the small amount like I did.

So see if you can find some clever way to do a lot of those breaking ups in one go, perhaps by trying a few small break ups yourself if you can't see it straight away.

EDIT: Sorry I didn't see your post VeeEight! I'll leave mine up here in case the OP doesn't know mod arithmetic.

 

[missavvy]

ah, thanks VeeEight!
i guess my prof skipped fermat's in our notes.
Thank you Gib Z! :)