Enter modulo statements

x=1mod2 x=2mod3 x=3mod5 x=4mod11
  

---

2x₁ + 165y₁ = 1
3x₂ + 110y₂ = 1
5x₃ + 66y₃ = 1
11x₄ + 30y₄ = 1

Answer

↓Steps Explained:↓

Using the Chinese Remainder Theorem, solve:

x ≡ 1 mod 2

x ≡ 2 mod 3

x ≡ 3 mod 5

x ≡ 4 mod 11

Pairwise Coprime: Take the GCF of 2 and modulus

GCF(2,11) = 1

Pairwise Coprime: Take the GCF of 3 and modulus

GCF(3,11) = 1

Pairwise Coprime: Take the GCF of 5 and modulus

GCF(5,11) = 1

Coprime check

Since all 6 GCF calculations 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₂ x n₃ x n₄

N = 2 x 3 x 5 x 11

N = 330

Determine Equation Coefficients c_i

ci  =	N
	ni

Calculate c₁

c1  =	330
	2

c₁ = 165

Calculate c₂

c2  =	330
	3

c₂ = 110

Calculate c₃

c3  =	330
	5

c₃ = 66

Calculate c₄

c4  =	330
	11

c₄ = 30

Our equation becomes:

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

x = a₁(165y₁) + a₂(110y₂) + a₃(66y₃) + a₄(30y₄)

Note: The a_i piece is factored out

We will use this below

Calculate each y₁

Using 1 modulus of 2 and c₁ = 165
calculate y₁ in the equation below:

y₁ = 1

Calculate each y₂

Using 2 modulus of 3 and c₂ = 110
calculate y₂ in the equation below:

y₂ = -1

Calculate each y₃

Using 3 modulus of 5 and c₃ = 66
calculate y₃ in the equation below:

y₃ = 1

Calculate each y₄

Using 4 modulus of 11 and c₄ = 30
calculate y₄ in the equation below:

y₄ = -4

Plug in y values

x = a₁(165y₁) + a₂(110y₂) + a₃(66y₃) + a₄(30y₄)

x = 1 x 165 x 1 + 2 x 110 x -1 + 3 x 66 x 1 + 4 x 30 x -4

x = 165 - 220 + 198 - 480

x = -337

Equation 1: Plug in -337 into modulus equations

-337 ≡ 1 mod 2

2 x -169 = -338

Add remainder of 1 to -338 = -337

Equation 2: Plug in -337 into modulus equations

-337 ≡ 2 mod 3

3 x -113 = -339

Add remainder of 2 to -339 = -337

Equation 3: Plug in -337 into modulus equations

-337 ≡ 3 mod 5

5 x -68 = -340

Add remainder of 3 to -340 = -337

Equation 4: Plug in -337 into modulus equations

-337 ≡ 4 mod 11

11 x -31 = -341

Add remainder of 4 to -341 = -337

Final Answer

-337

---

Take the Quiz  Switch to Chat Mode


Related Calculators:  Euclids Algorithm and Euclids Extended Algorithm  |  Diophantine Equations  |  Linear Congruential Generator