Post a New Question

Math

posted by on .

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

  • Math - ,

    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

Answer This Question

First Name:
School Subject:
Answer:

Related Questions

More Related Questions

Post a New Question