Posted by Shay on Thursday, August 2, 2012 at 5:37pm.
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
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 smallest positive integer that leaves a remainder of 5 when ...
maths - f(x)=px^3 + 6x^2 + 12x + q given that the remainder when f(x) is divided...
math - what is the least common positive integer that meets the following ...
math - what is the least common positive integer that meets the following ...
Math - 592 divided by 48 = 107 divided by 19 = Try using long division and ...
Math - Find the least positive integer that leaves the remainder 3 when divided...
math - When a positive integer, n, is divided by 24 the remainder is 18. When n...
For Further Reading
