{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 "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 
0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 256 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
257 "" 0 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 1 18 0 0 
0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 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 }{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 }1 0 
0 -1 -1 -1 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 -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 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 
{CSTYLE "" -1 -1 "" 0 1 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 "" 0 256 1 {CSTYLE "" -1 -1 "" 1 24 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 "" 0 257 1 
{CSTYLE "" -1 -1 "" 1 24 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 256 "" 0 "" {TEXT 256 36 "Computer Algebra, week \+
1, lecture 4:" }}{PARA 257 "" 0 "" {TEXT 257 18 "Modular arithmetic" }
{TEXT 258 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 23 "iquo = integer quotient" }}{PARA 0 "" 0 "" {TEXT -1 24 "i
rem = integer remainder" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "
iquo(80,12);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"'" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "irem(80,12);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#\"\")" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 90 "Means: if
 you divide 80 by 12, it fits 6 times, and the remainder is 8.  So 80 \+
= 6*12 + 8." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "80/12;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6##\"#?\"\"$" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 9 "evalf(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+nmm
mm!\"*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 109 "The command evalf comp
utes a floating point approximation (evalf = EVALuate Floating) of an \+
exact expression." }}{PARA 0 "" 0 "" {TEXT -1 482 "As you see above, t
here are different ways to divide integers. A division with / could pr
oduce an integer or a rational number. But there is also integer divis
ion, which always produces integers. In integer division, there is a q
uotient (iquo in Maple, short for: integer quotient. The command  quo \+
in Maple means quotient of polynomials and not integers) and there is \+
a remainder irem (again rem in Maple is for polynomials, and irem is i
nteger remainder, so irem is for integers)." }}{PARA 0 "" 0 "" {TEXT 
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 310 "In general, if you have positi
ve integers a,b, then integer division a by b means finding two intege
rs q and r such that a=q*b+r. Here q is the quotient and r is the rema
inder. Furthermore r must be smaller than b, and r must be greater or \+
equal than 0. That makes the quotient and remainder uniquely defined. \+
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "a:=80;" }}{PARA 11 "" 1 
"" {XPPMATH 20 "6#>%\"aG\"#!)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 6 "b:=12;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"bG\"#7" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "q:=iquo(a,b);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"qG\"\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
13 "r:=irem(a,b);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\"\")" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "a;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#\"#!)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "q*b+
r;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#!)" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 20 "So indeed a = q*b+r." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 23 "a:=2083475029337498275;" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%\"aG\"4v#)\\P$H]Z$3#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 8 "b:=1000;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"bG\"%+5" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "`Number of Digits of a` := l
ength(a);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%6Number~of~Digits~of~aG
\"#>" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "q:=iquo(a,b);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG\"1)\\P$H]Z$3#" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 61 "r:=irem(a,b);  # irem when b=10^3 gives y
ou the last 3 digits" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\"$v#" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "a = q*b + r;" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#/\"4v#)\\P$H]Z$3#F$" }}}{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; " }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>6%%#a1G%#a2G%#a3G6%\"(BXB#\"+nXduX\"/lawawa')" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 183 "r1, r2, r3 := seq(irem(a||i
,b), i=1..3);\n# Note: This is for Maple 6 and 7\n# To make it work in
 Maple 5 you must replace the || by a dot .\n# So in Maple 5 you have \+
a.i instead of a||i" }}{PARA 8 "" 1 "" {TEXT -1 14 "`|` unexpected" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "a1*a2*a3;" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#\"?ll&\\Zk3(\\<.?W*o%))" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 10 "irem(%,b);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$l&" 
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "r1*r2*r3;" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6#*(%#r1G\"\"\"%#r2GF%%#r3GF%" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 10 "irem(%,b);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#
-%%iremG6$*(%#r1G\"\"\"%#r2GF(%#r3GF(\"%+5" }}}{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, replace it with irem(K,b)\"." }}{PARA 0 "" 0 
"" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 238 "If we compute a1*a2*a
3 and then 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 modu
lo b, then take the product, and then reduce again modulo b. Another e
xample:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "b:=9;" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#>%\"bG\"\"*" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 29 "a1, a2, a3 :=1231, 3434, 123;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>6%%#a1G%#a2G%#a3G6%\"%J7\"%MM\"$B\"" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 39 "r1, r2, r3 := seq(irem(a||i,b),i=1..3);" 
}}{PARA 8 "" 1 "" {TEXT -1 14 "`|` unexpected" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 9 "a1+a2+a3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"%)
y%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "irem(%,b);" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 9 "r1+r2+r3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(%#r1G\"\"\"%#r2G
F%%#r3GF%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "irem(%,b);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#-%%iremG6$,(%#r1G\"\"\"%#r2GF(%#r3GF(
\"\"*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "135*a1^2*a2 + 98*a
3^12+a3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"=rFL>'>vDur0M^<\"" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "irem(%,b);" }}{PARA 11 "" 1 
"" {XPPMATH 20 "6#\"\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "
135*r1^2*r2 + 98*r3^12+r3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*&)%#r
1G\"\"#\"\"\"%#r2G\"\"\"\"$N\"*$)%#r3G\"#7F(\"#)*F.F*" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "irem(%,b);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#-%%iremG6$,(*&)%#r1G\"\"#\"\"\"%#r2G\"\"\"\"$N\"*$)%#r3
G\"#7F+\"#)*F1F-\"\"*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "ir
em(135,b)*r1^2*r2 + irem(98,b)*r3^12+r3;" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#,&*$)%#r3G\"#7\"\"\"\"\")F&\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 10 "irem(%,b);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%%irem
G6$,&*$)%#r3G\"#7\"\"\"\"\")F)\"\"\"\"\"*" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 273 "Whenever you have an expression with products and sums, \+
you can replace whatever you want in there by its remainder modulo b. \+
The expression will then change, but its remainder modulo b will not. \+
The following illustrates this, and illustrates the use of the Maple c
ommand " }{TEXT 259 3 "map" }{TEXT -1 1 "." }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 31 "V:=[112,2343,32445,1114,12345];" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#>%\"VG7'\"$7\"\"%VB\"&XC$\"%96\"&XB\"" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "map(hello,V);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#7'-%&helloG6#\"$7\"-F%6#\"%VB-F%6#\"&XC$-F%6#\"%96-F%6#
\"&XB\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "map(hello,V, x,y
,z);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7'-%&helloG6&\"$7\"%\"xG%\"yG%
\"zG-F%6&\"%VBF(F)F*-F%6&\"&XC$F(F)F*-F%6&\"%96F(F)F*-F%6&\"&XB\"F(F)F
*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "map(x -> x^2, V);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#7'\"&WD\"\"(\\'*[&\"+D!yE0\"\"('*4C\"
\"*D!*R_\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "map(x -> 1/x,
 V);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7'#\"\"\"\"$7\"#F%\"%VB#F%\"&X
C$#F%\"%96#F%\"&XB\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "ire
m( V[1]*V[2]+V[3]*V[4]*V[5] , 123);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6
#\"#R" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "V:=map(irem,V,123)
;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"VG7'\"$7\"\"\"'\"#'*\"\"(\"#X
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "irem( V[1]*V[2]+V[3]*V[
4]*V[5] , 123);" }{TEXT -1 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#R
" }}}{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)]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG-%'m
atrixG6#7&7&\"&TY\"\"&O2#\"&h&G\"&;%Q7&\"'^5;\"'K)[#\"'$Hr$\"'Cy`7&\"(
h:x\"\"(%)f)H\"(4o#[\"(O&Hv7&\")rr[>\")3=$e$\")<&[F'\"*/NT0\"" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "with(linalg):" }}{PARA 7 "" 
1 "" {TEXT -1 32 "Warning, new definition for norm" }}{PARA 7 "" 1 "" 
{TEXT -1 33 "Warning, new definition for trace" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 12 "d := det(A);" }}{PARA 11 "" 1 "" {XPPMATH 20 "
6#>%\"dG\"47$H7!=:hs*R" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "b:
=34;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"bG\"#M" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 10 "irem(d,b);" }}{PARA 11 "" 1 "" {XPPMATH 20 
"6#\"#?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "AA:=map( irem, A
, b);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#AAG-%'matrixG6#7&7&\"#@\"#
I\"\"\"F+7&\"#F\"#?\"#8\"#77&\"#D\"\"#\"#L\"#K7&\"\"$\"#CF*\"\"'" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "dd := det(AA);" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#>%#ddG\"'Cqo" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 11 "irem(dd,b);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#?" 
}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 353 "Note: If we only wanted to kno
w if matrix A is invertible or not, so if det(A) is zero or not, it wo
uld 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 wo
uld have shown that the determinant of A is non-zero modulo b, and hen
ce det(A) is non-zero, and A is invertible." }}{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;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#\"#?" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 206 "The comma
nd 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 c
alled the modulus. It is often denoted by m instead of b." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "m:=9;" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%\"mG\"\"*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "f:=293
* x^101 + 2134 * x^12 -2 * x^3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%
\"fG,(*$)%\"xG\"$,\"\"\"\"\"$$H*$)F(\"#7F*\"%M@*$)F(\"\"$F*!\"#" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "f mod m;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#,(*$)%\"xG\"$,\"\"\"\"\"\"&*$)F&\"#7F(\"\"\"*$)F&\"\"$F
(\"\"(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "v:=[123,4325345,1
5*x^15+12*x-1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG7%\"$B\"\"(X`
K%,(*$)%\"xG\"#:\"\"\"F,F+\"#7!\"\"\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 8 "v mod m;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"'
\"\"),(*$)%\"xG\"#:\"\"\"F$F)\"\"$F%\"\"\"" }}}{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;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\"\"$" }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 16 "r:=irem(-123,9);" }}{PARA 11 "" 1 "" {XPPMATH 20 "
6#>%\"rG!\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "q:=iquo(-12
3,9);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG!#8" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 6 "q*9+r;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#!$
B\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 139 "Maple's definition of iqu
o is such that the relation a*q+r=b still holds. You 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);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG\"
%G5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "r;" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#\"\"*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "q
:=iquo(12345,12,r);" }}{PARA 8 "" 1 "" {TEXT -1 60 "Error, wrong numbe
r (or type) of parameters in function iquo" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 94 "Do you remember from the worksheet on quotes what the rea
son is that it fails the 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 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 o
ne should stop the evaluation of r, as follows:" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 22 "q:=iquo(12345,12,'r');" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"qG\"%G5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
2 "r;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"*" }}}{EXCHG {PARA 0 "" 
0 "" {TEXT -1 148 "Now lets take some polynomials, multiply, and reduc
e all entries modulo 5. Then afterwards, lets first reduce, then multi
ply, and then reduce again." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
6 "p:=29;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"#H" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "f1 := x^4+randpoly(x,degree=3);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G,,*$)%\"xG\"\"%\"\"\"\"\"\"*$)F(
\"\"$F*!#&)*$)F(\"\"#F*!#bF(!#P!#NF+" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 31 "f2 := x^4+randpoly(x,degree=3);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%#f2G,,*$)%\"xG\"\"%\"\"\"\"\"\"*$)F(\"\"$F*\"#(**$)F(
\"\"#F*\"#]F(\"#z\"#cF+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "
f:=expand(f1*f2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,4%\"xG!%P[
*$)F&\"\"%\"\"\"!&LI\"*$)F&\"\"$F+!&]V\"*$)F&\"\"#F+!%`x!%g>\"\"\"*$)F
&\"\")F+F6*$)F&\"\"(F+\"#7*$)F&\"\"'F+!%]#)*$)F&\"\"&F+!%V&*" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "sort(f);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#,4*$)%\"xG\"\")\"\"\"\"\"\"*$)F&\"\"(F(\"#7*$)F&\"\"'F(
!%]#)*$)F&\"\"&F(!%V&**$)F&\"\"%F(!&LI\"*$)F&\"\"$F(!&]V\"*$)F&\"\"#F(
!%`xF&!%P[!%g>F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "f mod p;
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,4*$)%\"xG\"\")\"\"\"\"\"\"*$)F&\"
\"(F(\"#7*$)F&\"\"'F(\"#:*$)F&\"\"&F(\"#F*$)F&\"\"%F(\"#<*$)F&\"\"$F(F
4*$)F&\"\"#F(\"#>F&F0F-F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
13 "F1:=f1 mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#F1G,,*$)%\"xG
\"\"%\"\"\"\"\"\"*$)F(\"\"$F*\"\"#*$)F(F/F*F.F(\"#@\"#BF+" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "F2:=f2 mod p;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%#F2G,,*$)%\"xG\"\"%\"\"\"\"\"\"*$)F(\"\"$F*\"#5*$)F(
\"\"#F*\"#@F(F3\"#FF+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "F:
=expand(F1*F2) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"FG,4*$)%
\"xG\"\")\"\"\"\"\"\"*$)F(\"\"(F*\"#7*$)F(\"\"'F*\"#:*$)F(\"\"&F*\"#F*
$)F(\"\"%F*\"#<*$)F(\"\"$F*F6*$)F(\"\"#F*\"#>F(F2F/F+" }}}{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 modulo p\" because there are polynomials F1, F2 such th
at 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;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#,4*$)%\"xG\"\")\"\"\"\"\"\"*$)F&\"\"(F(\"#7*$)F&\"\"'F(
!%]#)*$)F&\"\"&F(!%V&**$)F&\"\"%F(!&LI\"*$)F&\"\"$F(!&]V\"*$)F&\"\"#F(
!%`xF&!%P[!%g>F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(
f);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&,,*$)%\"xG\"\"%\"\"\"\"\"\"*$
)F'\"\"$F)!#&)*$)F'\"\"#F)!#bF'!#P!#NF*F*,,F%F*F+\"#(*F/\"#]F'\"#z\"#c
F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "F;" }}{PARA 11 "" 1 
"" {XPPMATH 20 "6#,4*$)%\"xG\"\")\"\"\"\"\"\"*$)F&\"\"(F(\"#7*$)F&\"\"
'F(\"#:*$)F&\"\"&F(\"#F*$)F&\"\"%F(\"#<*$)F&\"\"$F(F4*$)F&\"\"#F(\"#>F
&F0F-F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(F);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#,4*$)%\"xG\"\")\"\"\"\"\"\"*$)F&\"\"(F
(\"#7*$)F&\"\"'F(\"#:*$)F&\"\"&F(\"#F*$)F&\"\"%F(\"#<*$)F&\"\"$F(F4*$)
F&\"\"#F(\"#>F&F0F-F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "% m
od p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,4*$)%\"xG\"\")\"\"\"\"\"\"*$
)F&\"\"(F(\"#7*$)F&\"\"'F(\"#:*$)F&\"\"&F(\"#F*$)F&\"\"%F(\"#<*$)F&\"
\"$F(F4*$)F&\"\"#F(\"#>F&F0F-F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 16 "factor(F) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,4*$)%\"xG
\"\")\"\"\"\"\"\"*$)F&\"\"(F(\"#7*$)F&\"\"'F(\"#:*$)F&\"\"&F(\"#F*$)F&
\"\"%F(\"#<*$)F&\"\"$F(F4*$)F&\"\"#F(\"#>F&F0F-F)" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 131 "The command factor(F) mod p does two things: firs
t it factors, then it reduces modulo p. The following command does som
ething else:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "K:=Factor(F
) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"KG*&,,*$)%\"xG\"\"%\"
\"\"\"\"\"*$)F)\"\"$F+\"\"#*$)F)F0F+F/F)\"#@\"#BF,F,,,F'F,F-\"#5F1F3F)
F3\"#FF,F," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 102 "The command factor
(F) searches for polynomials f1,f2,.. such that their product is exact
ly equal to F." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 213 "However, the command Factor(f) mod p; searches for polyn
omials f1,f2,.. such that the product f1*f2*... is not necessarily equ
al to F, the product 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);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,4%\"xG\"%]5*$)F$\"\"%\"\"\"\"
$l$*$)F$\"\"$F)\"$)y*$)F$\"\"#F)\"%05\"$@'\"\"\"*$)F$\"\")F)F4*$)F$\"
\"(F)\"#7*$)F$\"\"'F)\"#W*$)F$\"\"&F)\"$9\"" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 18 "Not the same as F." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 8 "% mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,4*$)%\"xG
\"\")\"\"\"\"\"\"*$)F&\"\"(F(\"#7*$)F&\"\"'F(\"#:*$)F&\"\"&F(\"#F*$)F&
\"\"%F(\"#<*$)F&\"\"$F(F4*$)F&\"\"#F(\"#>F&F0F-F)" }}}{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 t
he modulus is m, then the command \"mod m\" reduces all integers to in
tegers in the range 0..m-1. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 6 "m:=40;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG\"#S" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "k:=1/7 mod 40;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"kG\"#B" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 170 "The
re 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;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "1/15 mod 40;" }}{PARA 8 "" 1 "" 
{TEXT -1 41 "Error, the modular inverse does not exist" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 86 "This leads to an error because there is n
o k such that 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);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 12 "1/13 mod 40;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#P
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "igcd(22,40);" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 12 "1/22 mod 40;" }}{PARA 8 "" 1 "" {TEXT -1 41 "Error, the modula
r inverse does not exist" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 243 "A sp
ecial case is when the modulus m is a prime number. In that case we us
ually use the letter p. Now whenever an integer is reduced modulo p, i
t 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 modu
lo m you can divide by numbers that have igcd 1 with m, but modulo a p
rime 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;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"#>" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "v:=[seq(1/i,i=1..p-1)];" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#>%\"vG74\"\"\"#F&\"\"##F&\"\"$#F&\"\"%#F&\"
\"&#F&\"\"'#F&\"\"(#F&\"\")#F&\"\"*#F&\"#5#F&\"#6#F&\"#7#F&\"#8#F&\"#9
#F&\"#:#F&\"#;#F&\"#<#F&\"#=" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 11 "w:=v mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"wG74\"\"\"\"#
5\"#8\"\"&\"\"%\"#;\"#6\"#7\"#<\"\"#\"\"(\"\")\"\"$\"#:\"#9\"\"'\"\"*
\"#=" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "seq(w[i]*i, i=1..p-
1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "64\"\"\"\"#?\"#RF$F$\"#'*\"#xF&\"
$`\"F$F'F&F%\"$5#F)F&F(\"$C$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 10 "[%] mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#74\"\"\"F$F$F$F$F$
F$F$F$F$F$F$F$F$F$F$F$F$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 197 "Anot
her typical thing for prime numbers is that when a is non-zero modulo \+
p, then a^(p-1) reduces to 1 modulo p, which is called Fermat's little
 theorem (not the same as his famous \"last theorem\")." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "\{seq(i^(p-1) mod p,i=1..p-1)\};  #
 Fermat's little theorem holds:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<#
\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "p:=51;" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"#^" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 112 "\{seq(i^(p-1) mod p,i=1..p-1)\}; # Fermat's little t
heorem fails, which means that p=51 can not be a prime number." }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#<3\"#8\"#:\"#;\"#=\"#>\"#@\"#D\"#I\"#L
\"#M\"#O\"#U\"#V\"#\\\"\"\"\"\"%\"\"*" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 0 "" }}}}{MARK "123 1" 0 }{VIEWOPTS 1 1 0 1 1 1803 }