3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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

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

$\endgroup$
6
  • $\begingroup$ sorry could you please explain where the 69 and 68 came from? $\endgroup$ – Stu Mandersons Aug 24 '19 at 21:28
  • $\begingroup$ I've posted the details of the EEA in this case. Is that clearer now? $\endgroup$ – Bernard Aug 24 '19 at 21:50
  • $\begingroup$ sorry im still very lost. please bear in mind i am not a very bright math person $\endgroup$ – Stu Mandersons Aug 24 '19 at 22:33
  • $\begingroup$ 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. $\endgroup$ – Bernard Aug 24 '19 at 23:42
  • $\begingroup$ 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 $\endgroup$ – Stu Mandersons Aug 25 '19 at 6:44
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What jhappens if 2 is not a common factor? $\endgroup$ – Stu Mandersons Aug 25 '19 at 8:02
  • $\begingroup$ see everything past more generally. $\endgroup$ – user645636 Aug 25 '19 at 9:06
  • $\begingroup$ 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 $\endgroup$ – user645636 Aug 25 '19 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.