Using the Chinese Remainder Theorem, solve the following system of mod

August 2024 · 4 minute read
Image to Crop Enter modulo statements

Using the Chinese Remainder Theorem, solve:

x ≡ 9 mod 95

x ≡ 0 mod 97

x ≡ 30 mod 98

x ≡ 55 mod 99


Pairwise Coprime: Take the GCF of 95 and modulus

GCF(95,97) = 1

GCF(95,98) = 1

GCF(95,99) = 1


Pairwise Coprime: Take the GCF of 97 and modulus

GCF(97,98) = 1

GCF(97,99) = 1


Pairwise Coprime: Take the GCF of 98 and modulus

GCF(98,99) = 1


Coprime check

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 = 95 x 97 x 98 x 99

N = 89403930

Determine Equation Coefficients ci
ci  =  N
  ni

Calculate c1
c1  =  89403930
  95

c1 = 941094

Calculate c2
c2  =  89403930
  97

c2 = 921690

Calculate c3
c3  =  89403930
  98

c3 = 912285

Calculate c4
c4  =  89403930
  99

c4 = 903070

Our equation becomes:

x = a1(c1y1) + a2(c2y2) + a3(c3y3) + a4(c4y4)

x = a1(941094y1) + a2(921690y2) + a3(912285y3) + a4(903070y4)

Note: The ai piece is factored out

We will use this below

Calculate each y1

Using 1 modulus of 95 and c1 = 941094
calculate y1 in the equation below:

95x1 + 941094y1 = 1

y1 = 4

Calculate each y2

Using 2 modulus of 97 and c2 = 921690
calculate y2 in the equation below:

97x2 + 921690y2 = 1

y2 = 24

Calculate each y3

Using 3 modulus of 98 and c3 = 912285
calculate y3 in the equation below:

98x3 + 912285y3 = 1

y3 = 33

Calculate each y4

Using 4 modulus of 99 and c4 = 903070
calculate y4 in the equation below:

99x4 + 903070y4 = 1

y4 = 37

Plug in y values

x = a1(941094y1) + a2(921690y2) + a3(912285y3) + a4(903070y4)

x = 9 x 941094 x 4 + 0 x 921690 x 24 + 30 x 912285 x 33 + 55 x 903070 x 37

x = 338793840 + 903162150 + 1837747450

x = 2774788984

Equation 1: Plug in 2774788984 into modulus equations

2774788984 ≡ 9 mod 95

95 x 29208305 = 2774788975

Add remainder of 9 to 2774788975 = 2774788984

Equation 2: Plug in 2774788984 into modulus equations

2774788984 ≡ 0 mod 97

97 x 28606072 = 2774788984

Add remainder of 0 to 2774788984 = 2774788984

Equation 3: Plug in 2774788984 into modulus equations

2774788984 ≡ 30 mod 98

98 x 28314173 = 2774788954

Add remainder of 30 to 2774788954 = 2774788984

Equation 4: Plug in 2774788984 into modulus equations

2774788984 ≡ 55 mod 99

99 x 28028171 = 2774788929

Add remainder of 55 to 2774788929 = 2774788984

Final Answer

2774788984

You have 1 free calculations remaining


What is the Answer?

2774788984

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?

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

algorithmA process to solve a problem in a set amount of timechinese remainder theoremancient theorem that gives the conditions necessary for multiple equations to have a simultaneous integer solutioncoefficienta numerical or constant quantity placed before and multiplying the variable in an algebraic expressionequationa statement declaring two mathematical expressions are equalgcfgreatest common factor - largest positive integer dividing a set of integersmodulusthe remainder of a division, after one number is divided by another.
a mod bproductThe answer when two or more values are multiplied togetherremainderThe portion of a division operation leftover after dividing two integerssubstitutiona simple way to solve linear equations algebraically and find the solutions of the variables.theoremA statement provable using logic

Example calculations for the Chinese Remainder Theorem Calculator

Chinese Remainder Theorem Calculator Video


Tags:

Add This Calculator To Your Website

ncG1vNJzZmivp6x7rq3ToZqepJWXv6rA2GeaqKVfmLWqusSsnGeomKWMrq3Tq6CxaW2tcnN8nF5paXFVZ32uu8NeaWlxZVp9hXGPeq9eamBycnN8j15paaWfmXJzfJhwXGl8VWWOuXGRaXReamBofWZ%2Bj6amnV1iZYZ5cY99XGl5qFp%2FcYmEa2dubVVnfa67w15paXFpWn2FcY96XamkbYi8rcLEXmlpraOeu6hxkWl6oaGemsCmcZFpiZ6lkZ67pbHRXmlpjJiavLOxzA%3D%3D