(*^ ::[ Information = "This is a Mathematica Notebook file. It contains ASCII text, and can be transferred by email, ftp, or other text-file transfer utility. It should be read or edited using a copy of Mathematica or MathReader. If you received this as email, use your mail application or copy/paste to save everything from the line containing (*^ down to the line containing ^*) into a plain text file. On some systems you may have to give the file a name ending with ".ma" to allow Mathematica to recognize it as a Notebook. The line below identifies what version of Mathematica created this file, but it can be opened using any other version as well."; FrontEndVersion = "Macintosh Mathematica Notebook Front End Version 2.2"; MacintoshStandardFontEncoding; fontset = title, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, e8, 24, "Times"; fontset = subtitle, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, e6, 18, "Times"; fontset = subsubtitle, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeTitle, center, M7, italic, e6, 14, "Times"; fontset = section, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, grayBox, M22, bold, a20, 18, "Times"; fontset = subsection, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, blackBox, M19, bold, a15, 14, "Times"; fontset = subsubsection, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, whiteBox, M18, bold, a12, 12, "Times"; fontset = text, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = smalltext, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 10, "Times"; fontset = input, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeInput, M42, N23, bold, L-5, 12, "Courier"; fontset = output, output, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, L-5, 12, "Courier"; fontset = message, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, R65535, L-5, 12, "Courier"; fontset = print, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, L-5, 12, "Courier"; fontset = info, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, B65535, L-5, 12, "Courier"; fontset = postscript, PostScript, formatAsPostScript, output, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeGraphics, M7, l34, w282, h287, 12, "Courier"; fontset = name, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, italic, 10, "Geneva"; fontset = header, inactive, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = leftheader, inactive, L2, 12, "Times"; fontset = footer, inactive, noKeepOnOnePage, preserveAspect, center, M7, 12, "Times"; fontset = leftfooter, inactive, L2, 12, "Times"; fontset = help, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 10, "Times"; fontset = clipboard, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = completions, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = special1, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = special2, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = special3, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = special4, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = special5, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; paletteColors = 128; automaticGrouping; currentKernel; ] :[font = title; inactive; preserveAspect; startGroup] Chinese Remainder Theorem :[font = text; inactive; preserveAspect] The Chinese Remainder Theorem is a method to solve simultaneous congruences. There is a formula for the solutions to simultaneous congruences, but it is simpler to solve them 2 at a time. Suppose we have two congruences x = a (mod m) and x =b (mod n), where (m, n)=1. To solve this we can express 1 as a linear combination of m and n using the Extended Euclidean algorithm. Write u m + v n =1. Then a solution to the simultaneous congruence is x0= um b + vn a. Since vn is congruent to 1 modulo m, we have x0 = a (mod m). Similarly x0= b (mod n). The linear combination of u and v is found by the ExtendedGCD function. For example, consider x= 3 (mod 11) x= 7 (mod 18). First compute the ExtendedGCD of 11 and 18. ;[s] 8:0,1;482,2;483,1;550,2;552,1;576,2;577,1;800,0;807,-1; 3:1,13,9,Times,0,12,0,0,0;4,16,12,Times,0,14,0,0,0;3,24,16,Times,64,14,0,0,0; :[font = input; preserveAspect; startGroup] ExtendedGCD[11,18] :[font = output; output; inactive; preserveAspect; endGroup] {1, {5, -3}} ;[o] {1, {5, -3}} :[font = text; inactive; preserveAspect] The result is a list with two elements. The first element is the GCD and the second value gives the u and v such that 11 u + 18 v = GCD[11,18]=1. In this case, 11 (5) + 18 (-3) =1. Therefore the solution to our congruence is x= 11 (5) 7 + 18 (-3) 3. Lets verify that this satisfies the congruences. ;[s] 1:0,1;305,-1; 2:0,13,9,Times,0,12,0,0,0;1,16,12,Times,0,14,0,0,0; :[font = input; preserveAspect; startGroup] x= 11 5 7 + 18 (-3) 3 :[font = output; output; inactive; preserveAspect; endGroup] 223 ;[o] 223 :[font = input; preserveAspect; startGroup] Mod[x, 11] Mod[x, 18] :[font = output; output; inactive; preserveAspect] 3 ;[o] 3 :[font = output; output; inactive; preserveAspect; endGroup] 7 ;[o] 7 :[font = text; inactive; preserveAspect; fontSize = 14] This technique can be used to solve more than two simultaneous congruences. We solve them two at a time. Suppose we have the following simulataneous congruences: x= a1 (mod m1), x= a2 (mod m2), x=ak (mod mk), where the moduli mi are pairwise relatively prime. Then we solve the first two by the technique outlined above to get a solution x0 (mod m1m2). Now we have k-1 congruences: x= x0 (mod m1m2) x= a3 (mod m3) x= ak (mod mk) Here is the program which solves the simultaneous congruence. It takes two arguments, a list of values of ai and a corresponding list of values of mi. ;[s] 39:0,0;186,1;188,0;194,1;195,0;208,1;209,0;216,1;217,0;236,1;237,0;244,1;245,0;280,1;281,0;396,1;397,0;404,1;405,0;406,1;407,0;460,1;461,0;468,1;469,0;470,1;471,0;485,1;486,0;494,1;495,0;518,1;519,0;526,1;527,0;652,1;653,0;693,1;695,0;702,-1; 2:20,16,12,Times,0,14,0,0,0;19,24,16,Times,64,14,0,0,0; :[font = input; initialization; preserveAspect] *) crt[a_List, m_List]:= Module[ {i,x,n,k }, (*initialize*) i=1; x= a[[1]]; n=m[[1]]; If[ Length[a]== Length[m], (*then*)k=Length[a]; While[ i