1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple Algebra question about division/prime factorizations

  1. Mar 3, 2010 #1
    1. The problem statement, all variables and given/known data
    Find the remainder of the division of 7^211 by 11

    3. 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.. :)
     
  2. jcsd
  3. Mar 3, 2010 #2
    Use Fermat's Little Theorem, work modulo 11, and write 211 as 11x+y, for some integers x, y.
     
  4. Mar 3, 2010 #3

    Gib Z

    User Avatar
    Homework Helper

    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 [itex]7^{211}[/itex] for eg like this [itex] 7^2 X 7^{209}= 49 X 7^{209}[/itex]. 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;

    [tex]7^{211} = 7^2 x 7^{209} = (44 + 5) 7^{209} = 44X 7^{209} + 5X7^{209}[/tex]

    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.
     
  5. Mar 3, 2010 #4
    ah, thanks VeeEight!
    i guess my prof skipped fermat's in our notes.
    Thank you Gib Z! :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook