Asked by Adam

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

Answers

Answered by Steve
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.
There are no AI answers yet. The ability to request AI answers is coming soon!

Related Questions