Question

Write out in pseudo-code an algorithm for solving a simultaneous system of linear congruence based on the congruences based on the construction in the proof of the Chinese Reminder Theorem.

Short answer

The appropriate algorithm is given below.

Step 1: Find out common modulus M.

So,$M=m_1\cdot m_2\dots \dots \cdot m_n$

Step 2: Find the value of $M_i$

Where,$M_i=\frac{M}{m_i}$with respect to$m_1,m_2,\dots ,m_n$

Step 3: Find out inverse of$M_i$

Which is$M_1^{-1},M_2^{-1},\dots ,M_n^{-1}$with respect to$m_1,m_2,\dots ,m_n$

Step 4: Determine the solution which is given by,

$x\equiv \left(a_1{M}_1{M}_1^{-1}+a_2{M}_2{M}_2^{-1}+\dots +a_n{M}_n{M}_n^{-1}\right)(modM)$

Step-by-step solution

Chinese Remainder theorem

According to Chinese remainder theorem, let ${\mathit{m}}_{\mathbf{1}}\mathbf{,}{\mathit{m}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{m}}_{\mathit{r}}$be relatively prime numbers such that $\mathbf{(}{\mathbf{m}}_{\mathbf{i}}\mathbf{,}{\mathbf{m}}_{\mathbf{j}}\mathbf{)}\mathbf{=}\mathbf{1}$where $\mathbf{i}\mathbf{\ne }\mathbf{j}$then the linear congruences $\mathbf{x}\mathbf{\equiv }{\mathbf{a}}_{\mathbf{1}}\mathbf{(}\mathbf{mod}{\mathbf{m}}_{\mathbf{1}}\mathbf{)}\mathbf{,}\mathbf{x}\mathbf{\equiv }{\mathbf{a}}_{\mathbf{2}}\mathbf{(}\mathbf{mod}{\mathbf{m}}_{\mathbf{2}}\mathbf{)}\mathbf{,}\mathbf{\dots }\mathbf{,}\mathbf{x}\mathbf{\equiv }{\mathbf{a}}_{\mathbf{r}}\mathbf{(}\mathbf{mod}{\mathbf{m}}_{\mathbf{r}}\mathbf{)}$has a simultaneous solution which is unique modulo$\mathbf{(}{\mathbf{m}}_{\mathbf{1}}\mathbf{,}{\mathbf{m}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{m}}_{\mathbf{r}}\mathbf{)}$

Write appropriate algorithm

Let we have a system of congruence,

$x\equiv a_1\left(mod{m}_1\right),x\equiv a_2\left(mod{m}_2\right),\dots ,x\equiv a_n\left(mod{m}_n\right)$

Now, by Chinese remainder theorem,$m_1,m_2,\dots ,m_n$are relatively prime positive integer and$a_1,a_2,\dots ,a_n$are integers.

Step 1: Find out common modulus M.

So,localid="1668676551747" $M=m_1\cdot m_2\dots \dots \cdot m_n$

Step 2: Find the value of$M_i$

Where,$M_i=\frac{M}{m_i}$with respect to$m_1,m_2,\dots ,m_n$

Step 3: Find out inverse of$M_i$

Which is$M_1^{-1},M_2^{-1},\dots ,M_n^{-1}$with respect to$m_1,m_2,\dots ,m_n$

Step 4: Determine the solution which is given by,

$x\equiv \left(a_1{M}_1{M}_1^{-1}+a_2{M}_2{M}_2^{-1}+\dots +a_n{M}_n{M}_n^{-1}\right)(modM)$According to chemise remainder theorem.

Which is an appropriate solution for the Chinese Remainder Theorem.