{VERSION 6 0 "IBM INTEL LINUX" "6.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 3 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 } {PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 8 2 0 0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Error" 7 8 1 {CSTYLE "" -1 -1 "" 0 1 255 0 255 1 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "M aple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 0 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 }{PSTYLE "Author" 0 19 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 8 8 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 27 "Modular Arithmetic in Map le" }}}{EXCHG {PARA 19 "" 0 "" {TEXT -1 55 "Mike O'Sullivan\nSan Diego State University\nOctober 2004" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 205 "A key component of algebraic number theory is modular arithmetic. In this worksheet we will start with the basics of arithmetic in Z/n and then move on to polynomials over Z/n and linear algebra over Z/n. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 19 "Modular Arithmetic" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "Fortunately, Maple makes has some built in functions that make computing mod n simple." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "73 -590 mod 73;\n25*73 mod \+ 99;" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #\"#n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#V" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 69 "To make Maple think before it computes, use the \"neut ral operator\" &." }}{PARA 0 "" 0 "" {TEXT -1 177 "You'll see the diff erence here. In the first case it computes 66^1235346462356 and then \+ reduces. In the second it uses the repeated squaring method and reduc es as it proceeds." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "66^12 35346462356 mod 99;" }}{PARA 8 "" 1 "" {TEXT -1 35 "Error, numeric exc eption: overflow\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "66 &^ 1235346462356 mod 99;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 62 "Inverting mod n is simple. Of cou rse it isn't always defined." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "53^(-1) mod 99; \n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#r" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "66^(-1) mod 99;" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 8 "" 1 "" {TEXT -1 42 "Error, the m odular inverse does not exist\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 113 "Let u be a unit mod n . now consider all of the powers of u. We will see in class that the y must all be units. " }}{PARA 0 "" 0 "" {TEXT -1 102 "The first repe tition in the sequence u^k mod n for k = 0 to infinity is some r such \+ that u^r= 1 mod n." }}{PARA 0 "" 0 "" {TEXT -1 39 "We call r the \"ord er of u modulo n\". " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 19 "Here is an example." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "n:= 19;\n\nu := 4;\n " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"uG\"\"%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "for i from 1 to n do\n i, u^i mod n;\nod; \n " }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"\"\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"# \"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"$\"\"(" }}{PARA 11 "" 1 " " {XPPMATH 20 "6$\"\"%\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"&\" #<" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"'\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"(\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\")\"\" &" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"*\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#5\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#6\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#7\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#8\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#9\"#<" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#:\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#;\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#<\"\"& " }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#=\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#>\"\"%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 85 "So th e order of 2 mod 19 is 18.\nNow change the value of u and see what ord ers occur.\n" }}{PARA 0 "" 0 "" {TEXT -1 35 "You can also change the v alue of n." }}{PARA 0 "" 0 "" {TEXT -1 52 "Remember that you can only \+ find the order of a unit!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 9 "Exercises" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 98 "1) Write a procedure that, given u and n ,finds the order of u modulo n. Use \+ the for loop above." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 181 "2) Write a procedure that, given n, outputs each unit u and the order of that unit.\n\n3) Write a procedure that, given n, outputs the number of units mod n that have a given order." }}{PARA 0 "" 0 "" {TEXT -1 66 " That is count the number of elements of \+ order r and output " }}{PARA 0 "" 0 "" {TEXT -1 43 " r, the number of elements of order r.\n" }}{PARA 0 "" 0 "" {TEXT -1 54 "4) Experime nt! What orders do you get? And how many." }}}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 19 "Solving Polynomials" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 38 "You can also solve equations modulo m." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "mso lve(\{3*x-4*y=1,7*x+y=2\},19);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<$/% \"xG\"#:/%\"yG\"#6" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 110 "Integers a such that x^2 = a mod m has a solution (with a not congruent to 0) ar e called quadratic residues. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "msolve(x^2 = 5 , 17); #no solutions" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "msolve(x^2 = 8, 17);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$<#/%\"xG\"\"&<#/F%\"#7" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "msolve(x^2= 1, 8);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 &<#/%\"xG\"\"\"<#/F%\"\"$<#/F%\"\"&<#/F%\"\"(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 9 "Exercise s" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 84 "1) Find all quadratic residue s modulo 8. Find the number of square roots for each.\n" }}{PARA 0 " " 0 "" {TEXT -1 80 "2) Find all quadratic residues mod 15. Does x^2 \+ = 2y^2 mod 15 have a solution?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 66 "3) Write a procedure that computes all qu adratic residues mod n. " }}{PARA 0 "" 0 "" {TEXT -1 61 " Experim ent with different n. Can you form a conjecture?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 88 "4) How many solutions do you think a quadratic equation can have? How many on average?" }} {PARA 0 "" 0 "" {TEXT -1 40 " Can you think of some experiments? " }}}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{SECT 0 {PARA 3 " " 0 "" {TEXT -1 14 "Linear Algebra" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "Now let's do some linear algebra mod m;." }}{PARA 0 "" 0 "" {TEXT -1 57 "We need to include a package of linear algebra functions." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "with(LinearAlgebra:-Modular);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6 #7;%,AddMultipleG%(AdjointG%3BackwardSubstituteG%&BasisG%1ChineseRemai nderG%%CopyG%'CreateG%,DeterminantG%%FillG%2ForwardSubstituteG%)Identi tyG%(InverseG%(LUApplyG%0LUDecompositionG%,LinIntSolveG%)MatBasisG%'Ma tGcdG%$ModG%)MultiplyG%(PermuteG%'RandomG%*RowReduceG%%SwapG%*Transpos eG%'ZigZagG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "m := 19;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG\"#>" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 175 "The function RandomMatrix() chooses the entries of a matrix to be between -100 and +100.\n If you want the entries to be in a specified range, \+ then put in the generator clause." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "N := LinearAlgebra[RandomMatrix](2,2);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"NG-%'RTABLEG6%\"*WKNO\"-%'MATRIXG6#7$7$\"#i! #r7$!#z\"#G%'MatrixG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "N : = LinearAlgebra[RandomMatrix](2,2,generator=0..m-1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG-%'RTABLEG6%\"*OGON\"-%'MATRIXG6#7$7$\"#;\"\"! 7$\"#:F1%'MatrixG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 98 "Normally you can compute the inverse of a matrix, or the product very simply using M^(-1) or M.N.\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "Ninv : = N^(-1); N.N;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%NinvG-%'RTABLEG6 %\"*k\"z!Q\"-%'MATRIXG6#7$7$#\"\"\"\"#;\"\"!7$#!\"\"F0#F/\"#:%'MatrixG " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6%\"*Kx!p8-%'MATRIXG6#7$ 7$\"$c#\"\"!7$\"$l%\"$D#%'MatrixG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 42 "Here is how to do these computations mod m" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 38 "Ninv := Inverse(m,N); Multiply(m,N,N);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%%NinvG-%'RTABLEG6%\"*?8JQ\"-%'MATRIX G6#7$7$\"\"'\"\"!7$\"#8\"#9%'MatrixG" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#-%'RTABLEG6%\"*K+ZN\"-%'MATRIXG6#7$7$\"\"*\"\"!7$F,\"#;%'MatrixG" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 61 "I haven't found a way to exponent iate, so let's make our own." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 208 "Exponentiate := proc(m, N, r)\nlocal d, Pow, i;\n\nd := Dimensi on(N)[1];\n#Create the identity matrix.\nPow := Identity(m,d, integer) ; \nfor i from 1 to r do\n Pow := Multiply(m,Pow, N);\nod;\nRETURN(P ow);\nend proc;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%-ExponentiateGf*6%%\"mG%\"NG%\"rG6%%\"dG%$PowG% \"iG6\"F.C&>8$&-_%.LinearAlgebraG%*DimensionG6#9%6#\"\"\">8%-_%(Modula rG%)IdentityG6%9$F1%(integerG?(8&F:F:9&%%trueG>F<-_F?%)MultiplyG6%FBF< F8-%'RETURNG6#F " 0 "" {MPLTEXT 1 0 22 "Exponentiate(m,N,1);N;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6%\"*+i.N\"-%'MATRIXG6#7$7$ \"#8\"#:7$F,\"#9%'MatrixG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLE G6%\"*co,R\"-%'MATRIXG6#7$7$\"#8\"#:7$F,\"#9%'MatrixG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Determinant(m,N);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"'" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 9 "Exerci ses" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 71 "1) Solve some of the linea r congruence problems Rosen using matrices." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 91 "2) How many invertible 2x2 mat rices are there mod n? Try for a number of different n. " }}{PARA 0 "" 0 "" {TEXT -1 56 " Compare your results on the number of uni ts mod n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}}}}{MARK "8 17 1 4 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 } {RTABLE_HANDLES 136353244 135362836 138079164 136907732 138311320 135470032 }{RTABLE M7R0 I6RTABLE_SAVE/136353244X,%)anythingG6"6"[gl!"%!!!#%"#"#"#i!#z!#r"#GF& } {RTABLE M7R0 I6RTABLE_SAVE/135362836X,%)anythingG6"6"[gl!"%!!!#%"#"#"#;"#:""!F(F& } {RTABLE M7R0 I6RTABLE_SAVE/138079164X,%)anythingG6"6"[gl!"%!!!#%"#"##""""#;#!""F)""!#F("#:F& } {RTABLE M7R0 I6RTABLE_SAVE/136907732X,%)anythingG6"6"[gl!"%!!!#%"#"#"$c#"$l%""!"$D#F& } {RTABLE M7R0 I6RTABLE_SAVE/138311320X,%)anythingG6"6"[gl!"%!!!#%"#"#""'"#8""!"#9F& } {RTABLE M7R0 I6RTABLE_SAVE/135470032X,%)anythingG6"6"[gl!"%!!!#%"#"#""*F'""!"#;F& }