Posted by **Adam** on Monday, July 30, 2012 at 12:43pm.

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

- math -
**Steve**, Monday, July 30, 2012 at 2:19pm
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.

## Answer This Question

## Related Questions

- Math - How many integers between 200 and 500 inclusive leave a remainder 1 when ...
- Math - How many integers bewteen 200 and 500 inclusive leave a remainder 1 when ...
- Math adv function - An unknown polynomial f(x) of degree 37 yields a remainder ...
- Math - Find the least positive integer that leaves the remainder 3 when divided...
- math - 1.) when the expression 4x^2-3x-8 is divided by x-a, the remainder is 2. ...
- Math - Find the smallest positive integer that leaves a remainder of 5 when ...
- Math - repost for Anonymous - Can someone show me the steps to these questions (...
- number theory - Find the least positive integer that leaves the remainder 3 ...
- math - what is the least common positive integer that meets the following ...
- Math - This problem from China is almost 2000 years old: Find a number that when...

More Related Questions