{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 }{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 -1 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 665 "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, because quo means quotient of polynomials) and the
re is a remainder irem (again rem in Maple is for polynomials). In gen
eral, 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 qu
otient and r is the remainder. Furthermore r must be smaller than b, a
nd r must be greater or equal than 0. That makes the quotient and rema
inder 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 indeed a = q*b+r." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "a:=2083475029337498275;" }}}
{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 t
ake 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 number K >= b, rep
lace it with irem(K,b)\"." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "
" 0 "" {TEXT -1 238 "If we compute a1*a2*a3 and then reduce it modulo \+
b (that means: take the remainder irem(a1*a2*a3,b)) we get the same re
sult as when we first reduce a1,a2,a3 modulo b, then 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*a1^2*a2 + 98*a3^
12+a3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "irem(%,b);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "135*r1^2*r2 + 98*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 + irem(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 expression w
ith products and sums, you can replace whatever you want in there by i
ts remainder modulo b. The expression will then change, but its remain
der modulo b will not. The following illustrates this, and illustrates
 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] , 123);" }{TEXT -1 0 "
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 167 "The following is an example \+
about a determinant, then irem. Then we first do irem's in the matrix,
 take the determinant, and do irem. And again the result is the same.
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "A:=matrix(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 invertible or not, so i
f det(A) is zero or not, it would have been sufficient 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 the determinant of A
 is non-zero modulo b, and hence det(A) is non-zero, and A is invertib
le." }}{PARA 0 "" 0 "" {TEXT -1 50 " Instead of writing 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 exponents 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 mathematics 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:=iqu
o(-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 suc
h that the relation a*q+r=b still holds. You can also compute the quot
ient 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 you remember from the previou
s class what the reason is that it fails the second time?" }}{PARA 0 "
" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 223 "The optional thir
d argument of iquo and irem must be a name. 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 evaluation 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 polynomials, multiply, and reduce a
ll entries modulo 5. Then afterwards, lets 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+randpol
y(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 mod p;" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 23 "F:=expand(F1*F2) mod p;" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 314 "The polynomial f is an element of Q[x]. It is reducible,
 it equals f1*f2. The polynomial F equals f mod p. It is \"reducible m
odulo p\" because there are polynomials F1, F2 such that F1*F2 is cong
ruent 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, th
en 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 fo
r polynomials f1,f2,.. such that their product is exactly equal to F.
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 213 "Howe
ver, the command Factor(f) mod p; searches for polynomials f1,f2,.. su
ch that the product f1*f2*... is not necessarily equal to F, the produ
ct is only the same as F  when you reduce F and the product modulo p.
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "expand(K);" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 18 "Not 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\" reduces all integers to integers in the r
ange 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 product 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 th
at k*15 can reduce to 1 modulo 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 integers in this range have igcd 1 with p
,  except the number 0." }}{PARA 0 "" 0 "" {TEXT -1 242 "So modulo m y
ou can divide by numbers that 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 redu
ces 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 "Another typical thing for prime numbers is tha
t when a is non-zero modulo 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 i
s not." }}}}{MARK "126" 0 }{VIEWOPTS 1 1 0 1 1 1803 }