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 n_i 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 n_i's are pairwise coprime
We can use the regular CRT Formula

Calculate the moduli product N

Take the product of each n_i
N = n₁ x n₂ x n₃ x n₄
N = 2 x 3 x 5 x 11
N = 330

Determine Equation Coefficients c_i

c_i =	N
	n_i

Calculate c₁

c₁ =	330
	2

c₁ = 165

Calculate c₂

c₂ =	330
	3

c₂ = 110

Calculate c₃

c₃ =	330
	5

c₃ = 66

Calculate c₄

c₄ =	330
	11

c₄ = 30

Our equation becomes:

x = a₁(c₁y₁) + a₂(c₂y₂) + a₃(c₃y₃) + a₄(c₄y₄)
x = a₁(165y₁) + a₂(110y₂) + a₃(66y₃) + a₄(30y₄)
Note: The a_i piece is factored out
We will use this below

Calculate each y_i

Using 1 modulus of 2 and c₁ = 165
calculate y₁ in the equation below:
2x₁ + 165y₁ = 1
y₁ = 1

Using 2 modulus of 3 and c₂ = 110
calculate y₂ in the equation below:
3x₂ + 110y₂ = 1
y₂ = -1

Using 3 modulus of 5 and c₃ = 66
calculate y₃ in the equation below:
5x₃ + 66y₃ = 1
y₃ = 1

Using 4 modulus of 11 and c₄ = 30
calculate y₄ in the equation below:
11x₄ + 30y₄ = 1
y₄ = -4

Plug in y values

x = a₁(165y₁) + a₂(110y₂) + a₃(66y₃) + a₄(30y₄)
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

What is the Answer?

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 n_i 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?

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

Example calculations for the Chinese Remainder Theorem Calculator

x = 1 mod 2,x = 2 mod 3,x = 3 mod 5,x = 4 mod 11

Chinese Remainder Theorem Calculator Video

Tags:

Add This Calculator To Your Website