 # Using the Chinese Remainder Theorem, solve the following system of modulo equations: x=1mod2 x=2mod3 x=3mod5 x=4mod11

Enter modulo statements

Using the Chinese Remainder Theorem, solve:
x ≡ 1 mod 2
x ≡ 2 mod 3
x ≡ 3 mod 5
x ≡ 4 mod 11

## Check if ni is pairwise coprime

Take the GCF of 2 and modulus
GCF(2,3) = 1
GCF(2,5) = 1
GCF(2,11) = 1

Take the GCF of 3 and modulus
GCF(3,5) = 1
GCF(3,11) = 1

Take the GCF of 5 and modulus
GCF(5,11) = 1

Since all 6 GCF calculations equal 1
the ni's are pairwise coprime
We can use the regular CRT Formula

## Calculate the moduli product N

Take the product of each ni
N = n1 x n2 x n3 x n4
N = 2 x 3 x 5 x 11
N = 330

## Determine Equation Coefficients ci

 ci  = N ni

Calculate c1
 c1  = 330 2

c1 = 165

Calculate c2
 c2  = 330 3

c2 = 110

Calculate c3
 c3  = 330 5

c3 = 66

Calculate c4
 c4  = 330 11

c4 = 30

## Our equation becomes:

x = a1(c1y1) + a2(c2y2) + a3(c3y3) + a4(c4y4)
x = a1(165y1) + a2(110y2) + a3(66y3) + a4(30y4)
Note: The ai piece is factored out
We will use this below

## Calculate each yi

Using 1 modulus of 2 and c1 = 165
calculate y1 in the equation below:
2x1 + 165y1 = 1
y1 = 1

Using 2 modulus of 3 and c2 = 110
calculate y2 in the equation below:
3x2 + 110y2 = 1
y2 = -1

Using 3 modulus of 5 and c3 = 66
calculate y3 in the equation below:
5x3 + 66y3 = 1
y3 = 1

Using 4 modulus of 11 and c4 = 30
calculate y4 in the equation below:
11x4 + 30y4 = 1
y4 = -4

## Plug in y values

x = a1(165y1) + a2(110y2) + a3(66y3) + a4(30y4)
x = 1 x 165 x 1 + 2 x 110 x -1 + 3 x 66 x 1 + 4 x 30 x -4
x = 165 - 220 + 198 - 480
x = -337

## Plug in -337 into modulus equations

Equation 1:
-337 ≡ 1 mod 2
2 x -169 = -338
Add remainder of 1 to -338 = -337

Equation 2:
-337 ≡ 2 mod 3
3 x -113 = -339
Add remainder of 2 to -339 = -337

Equation 3:
-337 ≡ 3 mod 5
5 x -68 = -340
Add remainder of 3 to -340 = -337

Equation 4:
-337 ≡ 4 mod 11
11 x -31 = -341
Add remainder of 4 to -341 = -337

x = -337

x = -337

### How does the Chinese Remainder Theorem Calculator work?

Given a set of modulo equations in the form:
x ≡ a mod b
x ≡ c mod d
x ≡ e mod f

the calculator will use the Chinese Remainder Theorem to find the lowest possible solution for x in each modulus equation.
Given that the ni portions are not pairwise coprime and you entered two modulo equations, then the calculator will attempt to solve using the Method of Successive Subsitution
This calculator has 1 input.

### What 1 formula is used for the Chinese Remainder Theorem Calculator?

1. c = N/n

For more math formulas, check out our Formula Dossier

### What 10 concepts are covered in the Chinese Remainder Theorem Calculator?

algorithm
A process to solve a problem in a set amount of time
chinese remainder theorem
ancient theorem that gives the conditions necessary for multiple equations to have a simultaneous integer solution
coefficient
a numerical or constant quantity placed before and multiplying the variable in an algebraic expression
equation
a statement declaring two mathematical expressions are equal
gcf
greatest common factor - largest positive integer dividing a set of integers
modulus
the remainder of a division, after one number is divided by another.
a mod b
product
The answer when two or more values are multiplied together
remainder
The portion of a division operation leftover after dividing two integers
substitution
a simple way to solve linear equations algebraically and find the solutions of the variables.
theorem
A statement provable using logic