Using the Chinese Remainder Theorem, solve the following system of mod
Enter modulo statementsUsing the Chinese Remainder Theorem, solve:
x ≡ 4 mod 5
x ≡ 2 mod 7
x ≡ 2 mod 11
x ≡ 12 mod 13
Pairwise Coprime: Take the GCF of 5 and modulus
GCF(5,7) = 1
GCF(5,11) = 1
GCF(5,13) = 1
Pairwise Coprime: Take the GCF of 7 and modulus
GCF(7,11) = 1
GCF(7,13) = 1
Pairwise Coprime: Take the GCF of 11 and modulus
GCF(11,13) = 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 = 5 x 7 x 11 x 13
N = 5005
Determine Equation Coefficients ci
| ci = | N |
| ni |
Calculate c1
| c1 = | 5005 |
| 5 |
c1 = 1001
Calculate c2
| c2 = | 5005 |
| 7 |
c2 = 715
Calculate c3
| c3 = | 5005 |
| 11 |
c3 = 455
Calculate c4
| c4 = | 5005 |
| 13 |
c4 = 385
Our equation becomes:
x = a1(c1y1) + a2(c2y2) + a3(c3y3) + a4(c4y4)
x = a1(1001y1) + a2(715y2) + a3(455y3) + a4(385y4)
Note: The ai piece is factored out
We will use this below
Calculate each y1
Using 1 modulus of 5 and c1 = 1001
calculate y1 in the equation below:
Calculate each y2
Using 2 modulus of 7 and c2 = 715
calculate y2 in the equation below:
Calculate each y3
Using 3 modulus of 11 and c3 = 455
calculate y3 in the equation below:
Calculate each y4
Using 4 modulus of 13 and c4 = 385
calculate y4 in the equation below:
Plug in y values
x = a1(1001y1) + a2(715y2) + a3(455y3) + a4(385y4)
x = 4 x 1001 x 1 + 2 x 715 x 1 + 2 x 455 x 3 + 12 x 385 x 5
x = 4004 + 1430 + 2730 + 23100
x = 31264
Equation 1: Plug in 31264 into modulus equations
31264 ≡ 4 mod 5
Add remainder of 4 to 31260 = 31264
Equation 2: Plug in 31264 into modulus equations
31264 ≡ 2 mod 7
Add remainder of 2 to 31262 = 31264
Equation 3: Plug in 31264 into modulus equations
31264 ≡ 2 mod 11
Add remainder of 2 to 31262 = 31264
Equation 4: Plug in 31264 into modulus equations
31264 ≡ 12 mod 13
Add remainder of 12 to 31252 = 31264
Final Answer
31264
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 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
ncG1vNJzZmivp6x7rq3ToZqepJWXv6rA2GeaqKVfmLWqusSsnGeomKWMrq3Tq6CxaW2teGZ%2Fo2RrZKWfmXh2cY99XGl5qGBydJCKa2Kmp5RghGZ8o15nerBbWoCFd5FkpKicW2Z%2BZnyjXmd6sFtagIV3kGtipqeUYH50cs%2BldIynnKuybMHSoqWgY3Odtq%2Bx0p5ii52dlravsMSrYo2glaS%2Fprk%3D