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:
Calculate each y2
Using 2 modulus of 97 and c2 = 921690
calculate y2 in the equation below:
Calculate each y3
Using 3 modulus of 98 and c3 = 912285
calculate y3 in the equation below:
Calculate each y4
Using 4 modulus of 99 and c4 = 903070
calculate y4 in the equation below:
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
Add remainder of 9 to 2774788975 = 2774788984
Equation 2: Plug in 2774788984 into modulus equations
2774788984 ≡ 0 mod 97
Add remainder of 0 to 2774788984 = 2774788984
Equation 3: Plug in 2774788984 into modulus equations
2774788984 ≡ 30 mod 98
Add remainder of 30 to 2774788954 = 2774788984
Equation 4: Plug in 2774788984 into modulus equations
2774788984 ≡ 55 mod 99
Add remainder of 55 to 2774788929 = 2774788984
Final Answer
You have 2 free calculationss remaining
What is the Answer?
How does the Chinese Remainder Theorem Calculator work?
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?
- 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
Chinese Remainder Theorem Calculator Video
Tags:
Add This Calculator To Your Website
