Modular Arithmetic CRT: How do modulo with very big numbers

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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. $$