# Math

posted by .

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

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

Noting that 247=(13)(19), find the remainder when 13^18+19^12 is divided by 247
5. ### 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.
6. ### 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?
7. ### 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?
8. ### 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.
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 …

An unknown polynomial f(x) of degree 37 yields a remainder of 1 when divided by x – 1, a remainder of 3 when divided by x – 3, a remainder of 21 when divided by x – 5. Find the remainder when f(x) is divided by (x – 1)(x – …

More Similar Questions