Find the remainder when 13^18 + 19^12 is divided by 247.

Answer 1

Compute it mod 13 and mod 19 first.

19^12 = 1 Mod 13 by Fermat's little theorem.

And

13^18 = 1 Mod 19 by Fermat's little theorem.

So, we can write the answer as:

1*19 (19^(-1) Mod 13) +

1*13 (13^(-1) Mod 19)

Mod 19 the first term is zero, the second is 1, while Mod 13 the last term is zero while te first is 1, so both mod 13 and mod 19 we get the correct answer, therefore it is the right answer mod (13*19).

Computing the inverse Mod 13:

19 = 6

6*2 = 12 = -1, so

19^(-1) Mod 13 = -2

Computing the inverse Mod 19:

13 = -6

-6*3 = -18 = 1

So, we see that

13^(-1) Mod 19 = 3

We can thus write the answer as:

1*19 (19^(-1) Mod 13) +

1*13 (13^(-1) Mod 19) =

-2*19 + 3*13 = 1