Post a New Question

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

More Related Questions

Post a New Question