{VERSION 4 0 "IBM INTEL LINUX22" "4.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 }
{CSTYLE "" -1 256 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 
257 "" 0 18 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 1 18 0 
0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 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 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Outp
ut" -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 "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 "Maple Out
put" 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 "" 0 256 1 {CSTYLE "" -1 -1 "" 1 
24 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 "" 0 257 1 {CSTYLE "" -1 -1 "" 1 24 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 }}
{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 11 "" 1 "" {XPPMATH 20 "6#>6%%#r1G%#r2G%#
r3G6%\"$B&\"$n&\"$l%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "a1*a
2*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 "r
1*r2*r3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"*l:*y8" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 10 "irem(%,b);" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#\"$l&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 21 "Hey, that's the sa
me." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 90 "\"
Computing modulo b\" means: \"whenever you see a number K >= b, replac
e 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 resu
lt as when we first reduce a1,a2,a3 modulo b, then take the product, a
nd then reduce again modulo b. Another example:" }}}{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 11 "" 1 "" {XPPMATH 20 "6#>6%%#
r1G%#r2G%#r3G6%\"\"(\"\"&\"\"'" }}}{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+r
2+r3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#=" }}}{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*a1^2*a2 + 98*a3^
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#\"-4?qCL
@" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "irem(%,b);" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#\"\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 42 "irem(135,b)*r1^2*r2 + irem(98,b)*r3^12+r3;" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#\",%peUT<" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
10 "irem(%,b);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"'" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 273 "Whenever you have an expression with pro
ducts and sums, you can replace whatever you want in there by its rema
inder modulo b. The expression will then change, but its remainder mod
ulo b will not. The following illustrates this, and illustrates the us
e of the Maple command " }{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(h
ello,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 "ma
p(x -> 1/x, V);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7'#\"\"\"\"$7\"#F%
\"%VB#F%\"&XC$#F%\"%96#F%\"&XB\"" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 38 "irem( 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 "i
rem( 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 fo
llowing 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 th
e 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-%'matrixG6#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(l
inalg):" }}{PARA 7 "" 1 "" {TEXT -1 80 "Warning, the protected names n
orm and trace have been redefined and unprotected\n" }}}{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 know if matrix A is invertible or not, so if 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 t
han those of A. It would have shown that the determinant of A is non-z
ero modulo b, and hence det(A) is non-zero, and A is invertible." }}
{PARA 0 "" 0 "" {TEXT -1 50 " Instead of writing irem(dd,b) you can al
so 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 command mod will apply irem on every integer in sight, exc
ept exponents of polynomials. The b we've used so far, we were computi
ng modulo b, is called the modulus. It is often denoted by m instead o
f 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*&\"%M@F*)F(\"#7F
*F**&\"\"#F*)F(\"\"$F*!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
8 "f mod m;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*$)%\"xG\"$,\"\"\"\"
\"\"&*$)F&\"#7F(F(*&\"\"(F()F&\"\"$F(F(" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 32 "v:=[123,4325345,15*x^15+12*x-1];" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"vG7%\"$B\"\"(X`K%,(*$)%\"xG\"#:\"\"\"F,*&\"#7F-F+F-
F-F-!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "v mod m;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"'\"\"),(*$)%\"xG\"#:\"\"\"F$*&\"
\"$F+F)F+F+F%F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 266 "Note: In Mapl
e, if a<0 and b>0 then irem(a,b)<=0. In mathematics the usual definiti
on 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 de
finition 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(-123,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 iquo is such that the rela
tion a*q+r=b still holds. You can also compute the quotient and remain
der at the same time." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "res
tart;" }}}{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 61 "Error, wrong number (or type) of paramete
rs in function iquo\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 94 "Do you r
emember from the worksheet on quotes what the reason 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 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');" }}{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 le
ts take some polynomials, multiply, and reduce all entries modulo 5. T
hen afterwards, lets first reduce, then multiply, and then reduce agai
n." }}}{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*)F(
\"\"#F*F/*&\"#PF*F(F*F/\"#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**&\"#]F*)F(\"\"#F
*F**&\"#zF*F(F*F*\"#cF*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "
f:=expand(f1*f2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,4!%g>\"\"
\"*&\"%P[F'%\"xGF'!\"\"*&\"&LI\"F')F*\"\"%F'F+*&\"%V&*F')F*\"\"&F'F+*$
)F*\"\")F'F'*&\"#7F')F*\"\"(F'F'*&\"%]#)F')F*\"\"'F'F+*&\"&]V\"F')F*\"
\"$F'F+*&\"%`xF')F*\"\"#F'F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 8 "sort(f);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,4*$)%\"xG\"\")\"\"\"
F(*&\"#7F()F&\"\"(F(F(*&\"%]#)F()F&\"\"'F(!\"\"*&\"%V&*F()F&\"\"&F(F1*
&\"&LI\"F()F&\"\"%F(F1*&\"&]V\"F()F&\"\"$F(F1*&\"%`xF()F&\"\"#F(F1*&\"
%P[F(F&F(F1\"%g>F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "f mod \+
p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,4*$)%\"xG\"\")\"\"\"F(*&\"#7F()
F&\"\"(F(F(*&\"#:F()F&\"\"'F(F(*&\"#FF()F&\"\"&F(F(*&\"#<F()F&\"\"%F(F
(*&F4F()F&\"\"$F(F(*&\"#>F()F&\"\"#F(F(*&F0F(F&F(F(F*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
*)F(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**&\"#5F*)F(\"\"$F*F**&\"#@F*)F(\"\"#F*F**&F0F*F(F*F*
\"#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
**&\"#7F*)F(\"\"(F*F**&\"#:F*)F(\"\"'F*F**&\"#FF*)F(\"\"&F*F**&\"#<F*)
F(\"\"%F*F**&F6F*)F(\"\"$F*F**&\"#>F*)F(\"\"#F*F**&F2F*F(F*F*F,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 that F1*F2 is congruent to F modulo p (i.e. the have the same rem
ainder modulo p). This is something that Maple uses to factor polynomi
al." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#,4*$)%\"xG\"\")\"\"\"F(*&\"#7F()F&\"\"(F(F(*&\"%]#)F(
)F&\"\"'F(!\"\"*&\"%V&*F()F&\"\"&F(F1*&\"&LI\"F()F&\"\"%F(F1*&\"&]V\"F
()F&\"\"$F(F1*&\"%`xF()F&\"\"#F(F1*&\"%P[F(F&F(F1\"%g>F1" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(f);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#*&,,*$)%\"xG\"\"%\"\"\"F)*&\"#&)F))F'\"\"$F)!\"\"*&\"#b
F))F'\"\"#F)F.*&\"#PF)F'F)F.\"#NF.F),,F%F)*&\"#(*F)F,F)F)*&\"#]F)F1F)F
)*&\"#zF)F'F)F)\"#cF)F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "F
;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,4*$)%\"xG\"\")\"\"\"F(*&\"#7F()F
&\"\"(F(F(*&\"#:F()F&\"\"'F(F(*&\"#FF()F&\"\"&F(F(*&\"#<F()F&\"\"%F(F(
*&F4F()F&\"\"$F(F(*&\"#>F()F&\"\"#F(F(*&F0F(F&F(F(F*F(" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(F);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#,4*$)%\"xG\"\")\"\"\"F(*&\"#7F()F&\"\"(F(F(*&\"#:F()F&
\"\"'F(F(*&\"#FF()F&\"\"&F(F(*&\"#<F()F&\"\"%F(F(*&F4F()F&\"\"$F(F(*&
\"#>F()F&\"\"#F(F(*&F0F(F&F(F(F*F(" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 8 "% mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,4*$)%\"xG
\"\")\"\"\"F(*&\"#7F()F&\"\"(F(F(*&\"#:F()F&\"\"'F(F(*&\"#FF()F&\"\"&F
(F(*&\"#<F()F&\"\"%F(F(*&F4F()F&\"\"$F(F(*&\"#>F()F&\"\"#F(F(*&F0F(F&F
(F(F*F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "factor(F) mod p;
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,4*$)%\"xG\"\")\"\"\"F(*&\"#7F()F&
\"\"(F(F(*&\"#:F()F&\"\"'F(F(*&\"#FF()F&\"\"&F(F(*&\"#<F()F&\"\"%F(F(*
&F4F()F&\"\"$F(F(*&\"#>F()F&\"\"#F(F(*&F0F(F&F(F(F*F(" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 131 "The command factor(F) mod p does two thi
ngs: 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;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"KG*&,,*$)%\"x
G\"\"%\"\"\"F+*&\"\"#F+)F)\"\"$F+F+*&F/F+)F)F-F+F+*&\"#@F+F)F+F+\"#BF+
F+,,F'F+*&\"#5F+F.F+F+*&F3F+F1F+F+*&F3F+F)F+F+\"#FF+F+" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 102 "The command factor(F) searches for polyn
omials f1,f2,.. such that their product is exactly equal to F." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 213 "However,
 the command Factor(f) mod p; searches for polynomials f1,f2,.. such t
hat the product f1*f2*... is not necessarily equal to F, the product i
s 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\"$@'\"\"\"*&\"%]5F%%\"xGF%F%*&\"$l$F%)F(\"\"%F%F%
*&\"$9\"F%)F(\"\"&F%F%*$)F(\"\")F%F%*&\"#7F%)F(\"\"(F%F%*&\"#WF%)F(\"
\"'F%F%*&\"$)yF%)F(\"\"$F%F%*&\"%05F%)F(\"\"#F%F%" }}}{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(*&\"#7F()F&\"\"(F(F(*&\"#:F()F&\"\"'F(F(*&\"#FF()F&\"\"&F
(F(*&\"#<F()F&\"\"%F(F(*&F4F()F&\"\"$F(F(*&\"#>F()F&\"\"#F(F(*&F0F(F&F
(F(F*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 the modulus is m, then the command \"mod m
\" reduces all integers to integers 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 "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;" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
12 "1/15 mod 40;" }}{PARA 8 "" 1 "" {TEXT -1 42 "Error, the modular in
verse does not exist\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "This le
ads to an error because there is no k such that k*15 can reduce to 1 m
odulo 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 mod
ulo 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 42 "Error, the modular inverse does not exist\n" }}
}{EXCHG {PARA 0 "" 0 "" {TEXT -1 243 "A special case is when the modul
us 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 you can divide by numbe
rs 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 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#>%\"vG7
4\"\"\"#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 "Another typical thing for prime n
umbers 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 theorem 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 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }