Thread: Chinese remainder theorem
View Single Post
  #2  
Old December 15th, 2008, 03:18 PM
galactus's Avatar
galactus galactus is offline
Eater of Worlds

  
Join Date: Jul 2006
Location: Chaneysville, PA
Posts: 2,990
Country:
Thanks: 130
Thanked 1,146 Times in 1,031 Posts
galactus has much to be proud ofgalactus has much to be proud ofgalactus has much to be proud ofgalactus has much to be proud ofgalactus has much to be proud ofgalactus has much to be proud ofgalactus has much to be proud ofgalactus has much to be proud ofgalactus has much to be proud of
Default
The LCD is (4)(5)(7)=140

I like to do it like this:

Divide by the 'mods':

140/4=35, 140/5=28, 140/7=20

Now, find the inverses.

35p_{1}\equiv 1(mod \;\ 4)\Rightarrow p_{1}=3

28p_{2}\equiv 1(mod \;\ 5)\Rightarrow p_{2}=2

20p_{3}\equiv 1(mod \;\ 7)\Rightarrow p_{3}=6

Now, multiply:

(1)(35)(3)+(2)(28)(2)+(3)(20)(6)=577

x\equiv 577(mod 140)

\boxed{x=17}

Check the solution here:

Javascript Calculator

or the old-fashioned way:

\frac{17-1}{4}=4
\frac{17-2}{5}=3
\frac{17-3}{7}=2

Check.
Reply With Quote
The Following 2 Users Say Thank You to galactus For This Useful Post:
Donate to MHF