Given the following system of linear simultaneous congruences what is the value of x that satisfies them all? x≡18mod29 x≡20mod31 x≡6mod17

Question

Given the following system of linear simultaneous congruences what is the value of x that satisfies them all?  x≡18mod29  x≡20mod31  x≡6mod17

davonliefI · Accepted Answer

Step 1  According to the given information, it is required to find the value of x that satisfies all simultaneous congruence.  x≡18mod29  x≡20mod31  x≡6mod17  Step 2  Using Chinese remainder theorem:  Let m1,m2,….mr be a collection of pairwise relative prime integers.  then the system of simultaneous congruence  x≡a1(modm1)  x≡a2(modm2)  ....  x=ar(modmr)  has a unique solution modulo M=m1m2…mr for any integers a1,a2…,ar  Step 3  Now using the above theorem solve the given question.  a1=18,a2=20,a3=6  M=29×31×17=15283  m1=1528329=527  m2=1528331=493  m3=1528317=899  Step 4  Solving further:  m1m1―=1(mod29)⇒527m1―=1(mod29)  5m1―=1(mod29)⇒m1―=35  m2m2―=1(mod31)⇒493m2―=1(mod31)  −3m2―=1(mod31)⇒m2―=10  m3m3―=1(mod17)⇒899m3―=1(mod17)  15m3―=1(mod17)⇒m3―=8  Step 5  Therefore, the value of x is:  x=a1m1m1―+a2m2m2―+a3m3m3―  =(18×527×35)+(20×493×10)+(6×899×8)  =332010+98600+43152  =473762(mod15283)  x=15272

Given the following system of linear simultaneous congruences what is the value of x that satisfies them all? x -= 18 mod 29 x -= 20 mod 31 x -= 6 mod 17

Answered question

Answer & Explanation

New Questions in High school geometry