Chinese Remainder Theorem Calculator

Chinese Remainder Theorem Calculator Image to Crop

Enter Chinese Remainder Statements

Using the Chinese Remainder Theorem, solve:

x ≡ 4 mod 5

x ≡ 2 mod 7

Pairwise Coprime: Take the GCF of 5 and modulus

GCF(5,7) = 1

Coprime check

Since all 1 GCF calculation 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₂

N = 5 x 7

N = 35

Determine Equation Coefficients c_i

c_i =	N
	n_i

Calculate c₁

c₁ =	35
	5

c₁ = 7

Calculate c₂

c₂ =	35
	7

c₂ = 5

Our equation becomes:

x = a₁(c₁y₁) + a₂(c₂y₂)

x = a₁(7y₁) + a₂(5y₂)

Note: The a_i piece is factored out

We will use this below

Calculate each y₁

Using 1 modulus of 5 and c₁ = 7
calculate y₁ in the equation below:

5x₁ + 7y₁ = 1

y₁ = -2

Calculate each y₂

Using 2 modulus of 7 and c₂ = 5
calculate y₂ in the equation below:

7x₂ + 5y₂ = 1

y₂ = 3

Plug in y values

x = a₁(7y₁) + a₂(5y₂)

x = 4 x 7 x -2 + 2 x 5 x 3

x = -56 + 30

x = -26

Equation 1: Plug in -26 into modulus equations

-26 ≡ 4 mod 5

5 x -6 = -30

Add remainder of 4 to -30 = -26

Equation 2: Plug in -26 into modulus equations

-26 ≡ 2 mod 7

7 x -4 = -28

Add remainder of 2 to -28 = -26

Final Answer

-26

You have 1 free calculations remaining

What is the Answer?

How does the Chinese Remainder Theorem Calculator work?

Free Chinese Remainder Theorem Calculator - 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?

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