# 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

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

• so sorry but what is this u value? – Stu Mandersons Aug 24 '19 at 17:55
• Ahh, I'll edit the answer. one sec..:) – AgentS Aug 24 '19 at 17:56
• @StuMandersons I've edited the answer. Please see if it makes sense... – AgentS Aug 24 '19 at 17:59
• It all looks good now. Thanks @TheGreatDuck ! – AgentS Aug 24 '19 at 18:00
• Could you please explain how to break down a single equation into system of equations. I found it uses CRT, but could not understand. – Rajat Aggarwal Dec 5 '20 at 19:07

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

• sorry could you please explain where the 69 and 68 came from? – Stu Mandersons Aug 24 '19 at 21:28
• I've posted the details of the EEA in this case. Is that clearer now? – Bernard Aug 24 '19 at 21:50
• sorry im still very lost. please bear in mind i am not a very bright math person – Stu Mandersons Aug 24 '19 at 22:33
• You have to know the EEA is based on the remark that, during theEuclidean algorithm, not only the gcd (i.e. the last nonzero remainder) is a linear combination of the two given numbers, but actually the remainder at each step is such a linear combination. Furthermore, if we denote $u_i, v_i$ the coefficients at step $i$, these coefficients can be calculated recursively, since the relation $r_{i-1}=q_i r_i+r_ {i+1}$ can be written as $\;r_ {i+1}=r_{i-1}-q_i r_i$ and clearly, the same relation holds for the coefficients $u_i, v_i$. Try to do the calculations by hands since it's not very long. – Bernard Aug 24 '19 at 23:42
• sorry i dont suppose you can edit your answer to show this in detail please? i think im onto something but it would be great if you could just kindly show me that step – Stu Mandersons Aug 25 '19 at 6:44

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.

• What jhappens if 2 is not a common factor? – Stu Mandersons Aug 25 '19 at 8:02
• see everything past more generally. – user645636 Aug 25 '19 at 9:06
• Also roughly 40% of the time there will be a gcd that can be used, as roughly 60% of number pairs have Gcd 1 youtu.be/RZBhSi_PwHU?t=451 – user645636 Aug 25 '19 at 15:11