Chinese Remainder Theorem calculator

SolutionHelp

1. Chinese Remainder Theorem

1. x=2 (mod 5),x=3 (mod 7),x=10 (mod 11)

2. x=4 (mod 10),x=6 (mod 13),x=4 (mod 7),x=2 (mod 11)

3. x=6 (mod 11),x=13 (mod 16),x=9 (mod 21),x=19 (mod 25)

4. 3x=7 (mod 10)

5. 3x=6 (mod 12)

6. 2x=5 (mod 7),3x=4 (mod 8)

7. 2x=1 (mod 3),3x=5 (mod 8)

8. 2x=6 (mod 14),3x=9 (mod 15),5x=20 (mod 60)

9. x=3 (mod 7),x=3 (mod 5),x=4 (mod 12)

10. x=1 (mod 4),x=0 (mod 6)

2. Modulo

1. 42 mod 5

2. 3^302 mod 5

3. 19^24 mod 21

4. 7^106 mod 143

5. 27^400 mod 619

6. 42^-1 mod 5

3. Extended Euclidean Algorithm, Euclid's Algorithm, Modular multiplicative inverse

1. 11 and 12

2. 7 and 11

3. 3 and 7

Example

1. Chinese Remainder Theorem to solve $x=2 (mod 5),x=3 (mod 7),x=10 (mod 11)$

Solution:

$x-=2\ ("mod "5)->(1)$

$x-=3\ ("mod "7)->(2)$

$x-=10\ ("mod "11)->(3)$

$a_1=2,a_2=3,a_3=10$

$n_1=5,n_2=7,n_3=11$

Check if each $n_i$ is pairwise coprime

$GCD(5,7)=1$

$GCD(5,11)=1$

$GCD(7,11)=1$

since all gcd is 1, so each

$n_i$ is pairwise coprime

There is a unique solution modulo N

$N=n_1*n_2*n_3=5*7*11=385$

Step-1: $z_i = N / n_i$

$z_1 = N / n_1=385/5=77$

$z_2 = N / n_2=385/7=55$

$z_3 = N / n_3=385/11=35$

Step-2: find $y_i-=z_i^(-1)\ ("mod " n_i)$ using Extended Euclidean Algorithm

$y_1-=z_1^(-1)\ ("mod "n_1)-=77^(-1)\ ("mod "5)-=2^(-1)\ ("mod "5)-=-2\ ("mod "5)$

$t=-2$

i	Quotient $q=r_1-:r_2$	Remainder $r=r_1-q*r_2$	*$s=s_1-qs_2$**	*$t=t_1-qt_2$**
1		5	1	0
2		77	0	1
3	$5-:77=0$	$5-0xx77=5$	$1-0xx0=1$	$0-0xx1=0$
4	$77-:5=15$	$77-15xx5=2$	$0-15xx1=-15$	$1-15xx0=1$
5	$5-:2=2$	$5-2xx2=1$	$1-2xx-15=31$	$0-2xx1=-2$
6	$2-:1=2$	$2-2xx1=0$	$-15-2xx31=-77$	$1-2xx-2=5$

we get answer by taking the last non-zero row for Remainder r,

$t=-2$

$y_2-=z_2^(-1)\ ("mod "n_2)-=55^(-1)\ ("mod "7)-=6^(-1)\ ("mod "7)-=-1\ ("mod "7)$

$t=-1$

i	Quotient $q=r_1-:r_2$	Remainder $r=r_1-q*r_2$	*$s=s_1-qs_2$**	*$t=t_1-qt_2$**
1		7	1	0
2		55	0	1
3	$7-:55=0$	$7-0xx55=7$	$1-0xx0=1$	$0-0xx1=0$
4	$55-:7=7$	$55-7xx7=6$	$0-7xx1=-7$	$1-7xx0=1$
5	$7-:6=1$	$7-1xx6=1$	$1-1xx-7=8$	$0-1xx1=-1$
6	$6-:1=6$	$6-6xx1=0$	$-7-6xx8=-55$	$1-6xx-1=7$

we get answer by taking the last non-zero row for Remainder r,

$t=-1$

$y_3-=z_3^(-1)\ ("mod "n_3)-=35^(-1)\ ("mod "11)-=2^(-1)\ ("mod "11)-=-5\ ("mod "11)$

$t=-5$

i	Quotient $q=r_1-:r_2$	Remainder $r=r_1-q*r_2$	*$s=s_1-qs_2$**	*$t=t_1-qt_2$**
1		11	1	0
2		35	0	1
3	$11-:35=0$	$11-0xx35=11$	$1-0xx0=1$	$0-0xx1=0$
4	$35-:11=3$	$35-3xx11=2$	$0-3xx1=-3$	$1-3xx0=1$
5	$11-:2=5$	$11-5xx2=1$	$1-5xx-3=16$	$0-5xx1=-5$
6	$2-:1=2$	$2-2xx1=0$	$-3-2xx16=-35$	$1-2xx-5=11$

we get answer by taking the last non-zero row for Remainder r,

$t=-5$

Step-3: The solution, which is unique modulo 385, is

$x-=a_1*y_1*z_1+a_2*y_2*z_2+a_3*y_3*z_3\ ("mod "385)$

$:.x-=2*-2*77+3*-1*55+10*-5*35\ ("mod "385)$

$:.x-=-308-165-1750\ ("mod "385)$

$:.x-=-2223\ ("mod "385)$

$:.x-=87\ ("mod "385)$

Method-2: Successive substitution method

$x-=2\ ("mod "5)->(1)$

$x-=3\ ("mod "7)->(2)$

$x-=10\ ("mod "11)->(3)$

from (1)

$x-=2\ ("mod "5)$

Hence

$x=2+5a$

Now from (2),

$x-=3\ ("mod "7)$

$:. (2+5a)-=3\ ("mod "7)$

$:. 5a-=1\ ("mod "7)$

Here

$5^(-1)-=3\ ("mod "7)$

$:. 3xx5a-=3xx1\ ("mod "7)$

$:. 15a-=3\ ("mod "7)$

$:. a-=3\ ("mod "7)$

Hence

$a=3+7b$

But

$x=2+5a$

$:.x=2+5(3+7b)$

$:.x=2+15+35b$

$:.x=17+35b$

Now from (3),

$x-=10\ ("mod "11)$

$:. (17+35b)-=10\ ("mod "11)$

$:. 6+2b-=10\ ("mod "11)$

$:. 2b-=4\ ("mod "11)$

Here

$2^(-1)-=6\ ("mod "11)$

$:. 6xx2b-=6xx4\ ("mod "11)$

$:. 12b-=24\ ("mod "11)$

$:. b-=2\ ("mod "11)$

Hence

$b=2+11c$

But

$x=17+35b$

$:.x=17+35(2+11c)$

$:.x=17+70+385c$

$:.x=87+385c$

$:.x-=87\ ("mod "385)$