Using the Chinese Remainder Theorem, solve the following simultaneous congruence equations in x. Show all your working. 9x≡3mod15, 5x≡7mod21, 7x≡4mod13.

Question

Using the Chinese Remainder Theorem, solve the following simultaneous congruence equations in x. Show all your working.  9x≡3mod15,  5x≡7mod21,  7x≡4mod13.

pivonie8 · Accepted Answer

Step 1The given congruence equations are9x≡3mod155x≡7mod217x≡4mod13The first congruence can be converted to9x3≡33(mod153)3x≡1mod5   (By division property(ak≡bk(modngcd(n,k)))a≡bmodn)Now converting all the congruences fromax≡bmodnto x≡bmodnby multiplying b with inverse of a under modulo n.The obtained congruences arex≡2mod5x≡7mod21x≡8mod13Where n1=5,n2=21,n3=13,a1=2,a2=7,a3=8andgcd(n1,n2,n3)=1.Step 2Now using Chinese remainder theorem solution is obtained byx≡a1n1′y1+a2n2′y2+a3n3′y3(modN)→(⋅)Where N=n1n2n3=5×21×13=1365andn1′=Nn1=273n2′=Nn2=65n3′=Nn3=105and yi are inverse of ni′ under modulo ni, so calculating yi.y1=2y2=11y3=1Step 3Now substituting all the values in expression  (*) .x≡a1n1′y1+a2n2′y2+a3n3′y3(modN)x≡2×273×2+7×65×11+8×105×1(mod1365)x≡1092+5005+840(mod1365)

Using the Chinese Remainder Theorem, solve the following simultaneous congruence equations in x. Show all your working. 9x -= 3 mod 15, 5x -= 7 mod 21, 7x -= 4 mod 13.

Answered question

Answer & Explanation

New Questions in High school geometry