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.
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!
Submit Your Answer
We prioritize human answers over AI answers.
If you are human, and you can answer this question, please submit your answer.