# 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.

## 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 …