Modular Arithmetic CRT: How do modulo with very big numbers I have always been intrigued as to how one would calculate the modulo of a very large number without a calculator. This is an example that I have come up with just now:
4239^4 mod 19043
The answer is 808, but that is only because I used a calculator. I read in books and online that you can break the modulo 19043 to its factors such that it is modulo 137 and 139 as (modulo (137*139)) is (modulo 19043).
I tried something like this...
4239^4 mod 137
=129^4 mod 137
=123


4239^4 mod 139
=69^4 mod 139
=113

But now I am stuck as to what to do next in Chinese Remainder Theorem
 A: Solving $x\equiv 4239^4 \pmod {137\times 139}$ is equivalent to, from your work, solving the system:
$$x\equiv 123\pmod {137}\\x\equiv113\pmod{139}$$

First congruence implies we can write $x = 123 + 137k$ for some integer $k$.
Plug this in second congruence and solve $k$:
$$\begin{align}
123+137k &\equiv 113\pmod{139}\\
137k &\equiv -10\pmod{139}\\
-2k &\equiv -10\pmod{139}\\
k &\equiv 5\pmod{139}\\
\end{align}$$
That means we can write $k = 5+139u$ for some integer $u$.
Plug this back in $x$ : 
$$x=123+137k = 123+137(5+139u) = 808 + 137\times139u$$
A: You can use the general formula for the inverse isomorphism in the *Chinese remainder theorem:

If $ua+vb=1$ is a Bézout's relation between $a$ and $b$, then
  $$\begin{cases}x\equiv\alpha\mod a \\x\equiv \beta\mod b\end{cases} \iff x\equiv \beta ua+\alpha vb\mod ab.$$

Here , the extended Euclidean algorithm yields almost instantly
$$69\cdot 137-68\cdot 139=1, $$
so the solution is 
$$x\equiv 113\cdot 69\cdot 137-123\cdot 68\cdot 139=-94407\equiv -94407+5\cdot19043=808\mod 19043.$$
Note: $129^4\bmod 137$ is easier to compute by hand if you observe that it is $(-8)^4=2^{12}==2^7\cdot 2^5=(-9)\cdot 32=-288$.
Some details: here what the extended Euclidean algorithm yields in this case:
\begin{array}{rrrr}
r_i&u_i&v_i&q_i \\
\hline
139 & 0 & 1 \\
137 & 1 & 0 & 1 \\
\hline
2 & -1 & 1 & 68 \\
\color{red}1 & \color{red}{69} & \color{red}{-68} \\
\hline
\end{array}
Note: The extended Euclidean algorithm uses the observation that each remainder in the standard Euclidean algorithm can be expressed as a linear combination: 
if $r_i$ is the remainder at step $i$, there are coefficients $u_i,v_i$ such that $\; r_i=u_i a++v_i b$. As there is a recursion between these remainders: $\;r_{i-1}=q_ir_i+r_{i+1}\:$ ($q_i$ is the quotient at  $\text{step }i$), this relation can be written as
$$ r_{i+1}=r_{i-1}-q_ir_i,$$ 
and we have the same relation between the coefficient of  the linear combination:
$$ u_{i+1}=u_{i-1}-q_i u_i, \qquad  v_{i+1}=v_{i-1}-q_iv_i. $$
A: In this case, its as easy as: $$139-137=2\\123-113=5\cdot 2$$ meaning its: $$5\cdot 139+113\equiv 808 \bmod 19043$$ 
More generally, use the definition of mod: $$y\equiv b\bmod m\iff y=mx+b$$ and set the results mod the prime powers dividing your number equal, then solve:$$139z+113=137a+123\\2z=137(a-z)+10\\2(z-5)=137(a-z)\\-10=137a-139z$$ etc. 
