math

posted by .

find the remainder when 13^16 + 17^12 is divided by 221.

  • math -

    13 mod 221 = 13
    13^2 mod 221 = 169
    13^3 mod 221 = 208
    13^4 mod 221 = 52
    13^16 mod 221 = 52^4 mod 221 = 52

    17 mod 221 = 17
    17^2 mod 221 = 68
    17^3 mod 221 = 51
    17^4 mod 221 = 204
    17^12 mod 221 = 204^3 mod 221 = 170

    52 + 170 = 222 mod 221 = 1

    Hmmm. That's so simple, there must be an easier way to get it.

    Since 13 and 17 are relatively prime, we can find a,b such that

    13a + 17b = 1
    In fact, 13*21 - 17*16 = 1

    Now, letting n=13^16 + 17^12,
    n = 17^12 mod 13 = 1
    n = 13^16 mod 17 = 1

    so, n = 13*21 - 16*17 mod 221 = 1 mod 221

    Not so sure it's simpler, but it relies more on number theory.

Respond to this Question

First Name
School Subject
Your Answer

Similar Questions

  1. Math - repost for Anonymous

    Can someone show me the steps to these questions (I will provide the correct answers)?
  2. math

    what is the least common positive integer that meets the following conditions: divided by 7 with remainder 4 divided by 8 with remainder 5 divided by 9 with remainder 6 i thought you could add 7 and 4 to get 13, then divide 13 and …
  3. number theory

    Find the least positive integer that leaves the remainder 3 when divided by 7, remainder 4 when divided by 9, and remainder 8 when divided by 11
  4. Math

    Find the least positive integer that leaves the remainder 3 when divided by 7, remainder 4 when divided by 9, and remainder 8 when divided by 11. Using the Chinese Remainder Theorem.
  5. Math

    How many integers bewteen 200 and 500 inclusive leave a remainder 1 when divided by 7 and a remainder 3 when divided by 4?
  6. Math

    How many integers between 200 and 500 inclusive leave a remainder 1 when divided by 7 and a remainder 3 when divided by 4?
  7. Math

    Find the smallest positive integer that leaves a remainder of 5 when divided by 7, a remainder of 6 when divided by 11, and a remainder of 4 when divided by 13.
  8. Math

    This problem from China is almost 2000 years old: Find a number that when divided by 3 gives a remainder of 2, when divided by 5 gives a remainder of 3, and when divided by 7 gives a remainder of 4.
  9. math

    1.) when the expression 4x^2-3x-8 is divided by x-a, the remainder is 2. find the value of a. 2.) the polynomial 3x^3+mx^2+nx+5 leaves a remainder of 128 when divided by x-3 and a remainder of 4 when divided by x+1. calculate the remainder …
  10. Math adv function

    An unknown polynomial f(x) of degree 37 yields a remainder of 1 when divided by x – 1, a remainder of 3 when divided by x – 3, a remainder of 21 when divided by x – 5. Find the remainder when f(x) is divided by (x – 1)(x – …

More Similar Questions