Thursday

July 24, 2014

July 24, 2014

Posted by **Shay** on Thursday, August 2, 2012 at 5:37pm.

- Math -
**Count Iblis**, Thursday, August 2, 2012 at 6:07pmCompute 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

**Related Questions**

math - Noting that 247=(13)(19), find the remainder when 13^18+19^12 is divided...

Math - How many integers between 200 and 500 inclusive leave a remainder 1 when ...

Math - How many integers bewteen 200 and 500 inclusive leave a remainder 1 when ...

Math - Find the least positive integer that leaves the remainder 3 when divided...

Math - Find the smallest positive integer that leaves a remainder of 5 when ...

Math - repost for Anonymous - Can someone show me the steps to these questions (...

number theory - Find the least positive integer that leaves the remainder 3 ...

math - what is the least common positive integer that meets the following ...

Math - This problem from China is almost 2000 years old: Find a number that when...

math - This problem from China is almost 2000 years old: Find a number that when...