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.

Khadija Wells 2020-10-18 Answered
Using the Chinese Remainder Theorem, solve the following simultaneous congruence equations in x. Show all your working.
9x3mod15,
5x7mod21,
7x4mod13.
You can still ask an expert for help

Want to know more about Congruence?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Expert Answer

pivonie8
Answered 2020-10-19 Author has 91 answers
Step 1
The given congruence equations are
9x3mod15
5x7mod21
7x4mod13
The first congruence can be converted to
9x333(mod153)
3x1mod5 (By division property(akbk(modngcd(n,k)))abmodn)
Now converting all the congruences from
axbmodn
to
xbmodn
by multiplying b with inverse of a under modulo n.
The obtained congruences are
x2mod5
x7mod21
x8mod13
Where n1=5,n2=21,n3=13,a1=2,a2=7,a3=8andgcd(n1,n2,n3)=1.
Step 2
Now using Chinese remainder theorem solution is obtained by
xa1n1y1+a2n2y2+a3n3y3(modN)()
Where N=n1n2n3=5×21×13=1365
and
n1=Nn1=273
n2=Nn2=65
n3=Nn3=105
and yi are inverse of ni under modulo ni, so calculating yi.
y1=2
y2=11
y3=1
Step 3
Now substituting all the values in expression (*) .
xa1n1y1+a2n2y2+a3n3y3(modN)
x2×273×2+7×65×11+8×105×1(mod1365)
x1092+5005+840(mod1365)

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more