{VERSION 3 0 "SGI MIPS UNIX" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "" -1 256 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 } {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 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 256 19 "Modular arithmetic." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "iquo(80,12);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "irem(80,12);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 6 "80/12;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "evalf(%);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 109 "The command ev alf computes a floating point approximation (evalf = EVALuate Floating ) of an exact expression." }}{PARA 0 "" 0 "" {TEXT -1 453 "As you see \+ above, there are different ways to divide integers. The / could produc e an integer or a rational number. But there is also integer division, which always produces integers. In integer division, there is a quoti ent (iquo in Maple, short for: integer quotient. The command quo in M aple means quotient of polynomials) and there is a remainder irem (aga in rem in Maple is for polynomials, and irem is integer remainder, so \+ irem is for integers)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 310 "In general, if you have positive integers a,b, then integer division a by b means finding two integers q and r such that \+ a=q*b+r. Here q is the quotient and r is the remainder. Furthermore r \+ must be smaller than b, and r must be greater or equal than 0. That ma kes the quotient and remainder uniquely defined. " }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 6 "a:=80;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "b:=12;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "q:=iquo(a, b);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "r:=irem(a,b);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "a;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "q*b+r;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "So i ndeed a = q*b+r." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "a:=2083 475029337498275;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "b:=1000; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "`Number of Digits of a` := length(a);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "q:=iquo(a ,b);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "r:=irem(a,b);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "a = q*b + r;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "Now lets say we keep b fixed for a little while, and we take a couple of a's." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "a1, a2, a3 :=2234523, 4574574567, 86547654765465; " } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "r1, r2, r3 := seq(irem(a.i ,b), i=1..3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "a1*a2*a3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "irem(%,b);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "r1*r2*r3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "irem(%,b);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 21 "Hey, that's the same." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 90 "\"Computing modulo b\" means: \"whenever you see a n umber K >= b, replace it with irem(K,b)\"." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 238 "If we compute a1*a2*a3 and the n reduce it modulo b (that means: take the remainder irem(a1*a2*a3,b)) we get the same result as when we first reduce a1,a2,a3 modulo b, the n take the product, and then reduce again modulo b. Another example:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "b:=9;" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 29 "a1, a2, a3 :=1231, 3434, 123;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "r1, r2, r3 := seq(irem(a.i,b),i=1.. 3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "a1+a2+a3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "irem(%,b);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "r1+r2+r3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "irem(%,b);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "135*a 1^2*a2 + 98*a3^12+a3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "ir em(%,b);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "135*r1^2*r2 + 9 8*r3^12+r3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "irem(%,b);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "irem(135,b)*r1^2*r2 + ire m(98,b)*r3^12+r3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "irem(% ,b);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 271 "Whenever you have an exp ression with products and sums, you can replace whatever you want in t here by its remainder modulo b. The expression will then change, but i ts remainder modulo b will not. The following illustrates this, and il lustrates the use of the command map." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "V:=[112,2343,32445,1114,12345];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "map(hello,V);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "map(hello,V, x,y,z);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "map(x -> x^2, V);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "map(x -> 1/x, V);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "irem( V[1]*V[2]+V[3]*V[4]*V[5] , 123);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "V:=map(irem,V,123);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "irem( V[1]*V[2]+V[3]*V[4]*V[5] , 12 3);" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 167 "The follow ing is an example about a determinant, then irem. Then we first do ire m's in the matrix, take the determinant, and do irem. And again the re sult is the same." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "A:=mat rix(4,4,[seq(seq(i^j,i=11..14),j=4..7)]);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 13 "with(linalg):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "d := det(A);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "b:=34;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "irem(d,b);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "AA:=map( irem, A, b);" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "dd := det(AA);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "irem(dd,b);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 353 "Note: If we only wanted to know if matrix A is inve rtible or not, so if det(A) is zero or not, it would have been suffici ent to compute irem(det(AA),b). That computation is faster because the entries of AA are smaller than those of A. It would have shown that t he determinant of A is non-zero modulo b, and hence det(A) is non-zero , and A is invertible." }}{PARA 0 "" 0 "" {TEXT -1 50 " Instead of wri ting irem(dd,b) you can also write:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "dd mod b;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 206 "The command mod will apply irem on every integer in sight, except exponen ts of polynomials. The b we've used so far, we were computing modulo b , is called the modulus. It is often denoted by m instead of b." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "m:=9;" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 37 "f:=293* x^101 + 2134 * x^12 -2 * x^3;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "f mod m;" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 32 "v:=[123,4325345,15*x^15+12*x-1];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "v mod m;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 266 "Note: In Maple, if a<0 and b>0 then irem(a,b)<=0. In mat hematics the usual definition of remainder is such that the remainder \+ is always >=0. The command mod in Maple behaves like that definition, \+ \"a mod b\" is the usual definition of the integer remainder, it's >= \+ 0." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "r:= -123 mod 9;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "q:=(-123-K)/9;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "q*9+r;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "r:=irem(-123,9);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "q:=iquo(-123,9);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "q*9+r;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 139 "Maple' s definition of iquo is such that the relation a*q+r=b still holds. Yo u can also compute the quotient and remainder at the same time." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 20 "q:=iquo(12345,12,r);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 2 "r;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "q:=iquo(12345,12,r);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 89 "Do yo u remember from the previous class what the reason is that it fails th e second time?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 223 "The optional third argument of iquo and irem must be a n ame. Since r was evaluated to 9, the input really is 12345, 12, 9 and \+ so the third argument is not a name. To fix this one should stop the e valuation of r, as follows:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "q:=iquo(12345,12,'r');" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "r;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 148 "Now lets take some poly nomials, multiply, and reduce all entries modulo 5. Then afterwards, l ets first reduce, then multiply, and then reduce again." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "p:=29;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "f1 := x^4+randpoly(x,degree=3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "f2 := x^4+randpoly(x,degree=3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "f:=expand(f1*f2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "sort(f);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "f mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "F1:=f1 mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "F2:=f2 mo d p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "F:=expand(F1*F2) mo d p;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 314 "The polynomial f is an e lement of Q[x]. It is reducible, it equals f1*f2. The polynomial F equ als f mod p. It is \"reducible modulo p\" because there are polynomial s F1, F2 such that F1*F2 is congruent to F modulo p (i.e. the have the same remainder modulo p). This is something that Maple uses to factor polynomial." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(f);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "F;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(F);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "% mod \+ p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "factor(F) mod p;" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 131 "The command factor(F) mod p does \+ two things: first it factors, then it reduces modulo p. The following \+ command does something else:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "K:=Factor(F) mod p;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 102 "The command factor(F) searches for polynomials f1,f2,.. such that their p roduct is exactly equal to F." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 213 "However, the command Factor(f) mod p; se arches for polynomials f1,f2,.. such that the product f1*f2*... is not necessarily equal to F, the product is only the same as F when you r educe F and the product modulo p." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "expand(K);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "No t the same as F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "% mod p; " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "That's equal to F." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 100 "If the modulus is m, then the command \"mod m\" red uces all integers to integers in the range 0..m-1. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "m:=40;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "k:=1/7 mod 40;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 170 "There is a unique integer k in the range 0..m-1 such that the pro duct k*7 reduces to 1 modulo m. Therefore, 1/7 will be reduced to that integer k when computing modulo m." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "k*7 mod 40;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "1/15 mod 40;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "This leads \+ to an error because there is no k such that k*15 can reduce to 1 modul o 40." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 99 " In general, there exists a number k such that k*a reduces to 1 modulo \+ m if and only if igcd(a,m)=1." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "igcd(13,40);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "1/13 \+ mod 40;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "igcd(22,40);" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "1/22 mod 40;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 243 "A special case is when the modulus m is \+ a prime number. In that case we usually use the letter p. Now whenever an integer is reduced modulo p, it ends up in the range 0..p-1. All i ntegers in this range have igcd 1 with p, except the number 0." }} {PARA 0 "" 0 "" {TEXT -1 242 "So modulo m you can divide by numbers th at have igcd 1 with m, but modulo a prime p you can divide by any non- zero element (note that by non-zero I mean: non-zero after it has been reduced modulo p. Every multiple of p reduces to 0 modulo p)." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "p:=19;" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 23 "v:=[seq(1/i,i=1..p-1)];" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 11 "w:=v mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "seq(w[i]*i, i=1..p-1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "[%] mod p;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 112 "A nother typical thing for prime numbers is that when a is non-zero modu lo p, then a^(p-1) reduces to 1 modulo p." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 30 "\{seq(i^(p-1) mod p,i=1..p-1)\};" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "p:=51;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "\{seq(i^(p-1) mod p,i=1..p-1)\};" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 38 "So 29 is a prime number and 51 is not." }}}}{MARK "5 2 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 }