Enter modulo statements

  

Using the Chinese Remainder Theorem, solve:

x ≡ 0 mod 4

x ≡ 1 mod 5


Pairwise Coprime: Take the GCF of 4 and modulus

GCF(4,5) = 1


Coprime check

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

N = 4 x 5

N = 20

Determine Equation Coefficients ci

ci  =  N
  ni

Calculate c1

c1  =  20
  4

c1 = 5

Calculate c2

c2  =  20
  5

c2 = 4

Our equation becomes:

x = a1(c1y1) + a2(c2y2)

x = a1(5y1) + a2(4y2)

Note: The ai piece is factored out

We will use this below

Calculate each y1

Using 1 modulus of 4 and c1 = 5
calculate y1 in the equation below:

4x1 + 5y1 = 1

y1 = 1

Calculate each y2

Using 2 modulus of 5 and c2 = 4
calculate y2 in the equation below:

5x2 + 4y2 = 1

y2 = -1

Plug in y values

x = a1(5y1) + a2(4y2)

x = 0 x 5 x 1 + 1 x 4 x -1

x = 0 - 4

x = -4

Equation 1: Plug in -4 into modulus equations

-4 ≡ 0 mod 4

4 x -1 = -4

Add remainder of 0 to -4 = -4

Equation 2: Plug in -4 into modulus equations

-4 ≡ 1 mod 5

5 x -1 = -5

Add remainder of 1 to -5 = -4

Final Answer

-4


You have 2 free calculationss remaining



What is the Answer?
-4
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 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?

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
  1. 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




An Automated Online Math Tutor serving 8.1 million parents and students in 235 countries and territories.

Our Services

Top Categories

Community