{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 }
{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 1 }{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 1 }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 1 }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 1 }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 1 }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 1 }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 
1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }}
{SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT 256 37 "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 40 "r1, r2, r3 := seq(irem(a||i,
b), i=1..3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6%%#r1G%#r2G%#r3G6%\"
$B&\"$n&\"$l%" }}}{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*r
2*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 same.
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 90 "\"Com
puting modulo b\" means: \"whenever you see a number K >= b, replace i
t with irem(K,b)\"." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "
" {TEXT -1 256 "If we compute a1*a2*a3 and then reduce it modulo b (th
at means: take the remainder irem(a1*a2*a3,b)) we saw above that we ge
t the same result 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;" }}{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 "ir
em(%,b);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "
> " 0 "" {MPLTEXT 1 0 9 "r1+r2+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*r
2 + 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 products and sums, you can replac
e 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 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(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#>%\"AGK%'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\"Q(pprint0
6\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "with(linalg):" }}
{PARA 7 "" 1 "" {TEXT -1 80 "Warning, the protected names norm and tra
ce have been redefined and unprotected\n" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 12 "d := det(A);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"d
G\"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#>%#AAGK%'matrixG6#7&7&\"#@\"#I\"\"\"
F+7&\"#F\"#?\"#8\"#77&\"#D\"\"#\"#L\"#K7&\"\"$\"#CF*\"\"'Q(pprint16\"
" }}}{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 comput
ation 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, a
nd hence 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 com
mand mod will apply irem on every integer in sight, except exponents o
f 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;" }}{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,(*&\"$$H\"\"\")%\"xG\"$,\"F(F(*&\"%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&F&*$)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%,(*&\"#:\"\"\")%\"xGF*F+F+*&\"#7
F+F-F+F+F+!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "v mod m;
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"'\"\"),(*&F$\"\"\")%\"xG\"#:
F(F(*&\"\"$F(F*F(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 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;" }}{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 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);" }}{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 parameters in function iquo\n" }}}{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*\"#N!\"\"
*&\"#&)F*)F(\"\"$F*F,*&\"#bF*)F(\"\"#F*F,*&\"#PF*F(F*F," }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "f2 := x^4+randpoly(x,degree=3);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f2G,,*$)%\"xG\"\"%\"\"\"F*\"#cF**&
\"#(*F*)F(\"\"$F*F**&\"#]F*)F(\"\"#F*F**&\"#zF*F(F*F*" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "f:=expand(f1*f2);" }}{PARA 11 "" 1 
"" {XPPMATH 20 "6#>%\"fG,4\"%g>!\"\"*&\"%P[\"\"\"%\"xGF*F'*&\"&LI\"F*)
F+\"\"%F*F'*&\"&]V\"F*)F+\"\"$F*F'*&\"%`xF*)F+\"\"#F*F'*$)F+\"\")F*F**
&\"#7F*)F+\"\"(F*F**&\"%]#)F*)F+\"\"'F*F'*&\"%V&*F*)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#>%#F
1G,,*$)%\"xG\"\"%\"\"\"F*\"#BF**&\"\"#F*)F(\"\"$F*F**&F/F*)F(F-F*F**&
\"#@F*F(F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "F2:=f2 mod \+
p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#F2G,,*$)%\"xG\"\"%\"\"\"F*\"#
FF**&\"#5F*)F(\"\"$F*F**&\"#@F*)F(\"\"#F*F**&F1F*F(F*F*" }}}{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 red
ucible, it equals f1*f2. The polynomial F equals f mod p. It is \"redu
cible modulo p\" because there are polynomials 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;" }}{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)\"#N!\"\"*&\"#&)F))F'\"\"$F)F+*&\"#bF))F'\"\"#F)F+
*&\"#PF)F'F)F+F),,F%F)\"#cF)*&\"#(*F)F.F)F)*&\"#]F)F2F)F)*&\"#zF)F'F)F
)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 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;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"KG*&,,*$)%\"xG\"\"%\"\"\"F+\"#BF+*
&\"\"#F+)F)\"\"$F+F+*&F0F+)F)F.F+F+*&\"#@F+F)F+F+F+,,F'F+\"#FF+*&\"#5F
+F/F+F+*&F4F+F2F+F+*&F4F+F)F+F+F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
102 "The command factor(F) searches for polynomials 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 that the product f1*f2*... is
 not necessarily equal to F, the product is only the same as F  when y
ou 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%*&\"$)yF%)F(\"\"$F%F%*&\"
%05F%)F(\"\"#F%F%*$)F(\"\")F%F%*&\"#7F%)F(\"\"(F%F%*&\"#WF%)F(\"\"'F%F
%*&\"$9\"F%)F(\"\"&F%F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "Not th
e 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 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 42 "Error, the modular inverse does not exist\n" }}}{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 42 "Error, the modula
r inverse does not exist\n" }}}{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 mo
dulo m you 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 o
f 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 "0 2 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 
1 }{PAGENUMBERS 0 1 2 33 1 1 }