{VERSION 5 0 "IBM INTEL NT" "5.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 Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "" -1 256 "" 0 1 0 128 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1
257 "" 0 1 0 128 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0
128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 128 128 128 1
0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 128 1 0 0 0 0 0 0 0
0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 262 "" 0 1 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1
263 "" 0 1 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0
0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 128 1 0 0 0
0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 128 1 0 0 0 0 0 0 0 0 0 0
}{CSTYLE "" -1 267 "" 0 1 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE ""
-1 268 "" 0 1 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1
0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 128 1 0 0
0 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0
}{CSTYLE "" -1 272 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1
273 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0
0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 1 0 0 0 0 0
0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }
{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2
2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1" -1 3 1
{CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8
4 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Times
" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 2 1 0 1 0 2 2 0 1 }
{PSTYLE "Normal" -1 256 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 1 2 2
2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }}
{SECT 0 {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 257 38 "High School Modul
es > Advanced Topics\n" }}{PARA 3 "" 0 "" {TEXT -1 4 " " }{TEXT
256 18 "Modular Arithmetic" }}{PARA 0 "" 0 "" {TEXT -1 87 "\nAn explor
ation of modular arithmetic - adding, multiplying, powers, orders, res
idues.\n" }}{PARA 0 "" 0 "" {TEXT 258 153 "[Directions : Execute the C
ode Resource section first. Although there will be no output immediate
ly, these definitions are used later in this worksheet.]" }}{PARA 0 "
" 0 "" {TEXT -1 0 "" }}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 3 " " }
{TEXT 260 7 "0. Code" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "rest
art; with(plots): " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 420 "ModT
able := proc(n)\n local A,i,j,k,m;\n m := floor( n*3/2 + 3);\n
A := array( [seq( [ seq(` `, j = 1..(n) ) ], i = 1..m) ]);\n \+
A[1,1] := cat(`mod `,n); \n for k from 1 to n do A[2, k] \+
:= k-1; od;\n for k from 1 to n do A[3, k] := `__`; od;\n \n \+
\n for i from 1 to m-3 do \n for j from 1 to n do \n \+
A[i+3,j] := (n*(i-1)+j-1) ; od;od;\n \n print(A);\n \+
end proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 504 "ModAddTable \+
:= proc(n)\n local A,i,j,k;\n \n A := array( [seq( [ seq(`
`, j = 1..(n+3) ) ], i = 1..(n+3)) ]);\n A[1,1] := n; A[2
,2] := `+`;\n for k from 1 to n do A[1,k+3] := k-1; od;\n for \+
k from 1 to n do A[k+3, 1] := k-1; od;\n for k from 0 to n do A[
2,k+3] := `__`; od;\n for k from 0 to n do A[k+3, 2] := `|`; od;
\n \n for i from 1 to n do \n for j from 1 to n do \n \+
A[i+3,j+3] := (i + j -2) mod n ; od;od;\n \n print(A);
\n end proc:\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 506 "Mod
MultTable := proc(n)\n local A,i,j,k;\n \n A := array( [seq
( [ seq(` `, j = 1..(n+3) ) ], i = 1..(n+3)) ]);\n A[1,1] := n; \+
A[2,2] := `*`;\n for k from 1 to n do A[1,k+3] := k-1; od;
\n for k from 1 to n do A[k+3, 1] := k-1; od;\n for k from 0 t
o n do A[2,k+3] := `__`; od;\n for k from 0 to n do A[k+3, 2] :=
`|`; od;\n \n for i from 1 to n do \n for j from 1 to n d
o \n A[i+3,j+3] := ((i-1)*(j-1)) mod n ; od;od;\n \n
print(A);\n end proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1
0 536 "ModPowTable := proc(n)\n local A,i,j,k;\n \n A := ar
ray( [seq( [ seq(` `, j = 1..(n+2) ) ], i = 1..(n+2)) ]);\n A[1,
1] := cat(`mod `,n); A[1,2] := `powers :`; A[2,1] := `k :`;\n \+
for k from 1 to n do A[1,k+2] := k; od;\n for k from 1 to n do
A[k+2, 1] := k-1; od;\n for k from 1 to n do A[2,k+2] := `__`;
od;\n for k from 1 to n do A[k+2, 2] := `|`; od;\n \n for i f
rom 1 to n do \n for j from 1 to n do \n A[i+2,j+
2] := (i-1)^j mod n ; od;od;\n \n print(A);\n end proc:\n\n
" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 3 " " }{TEXT 262 34 "1. Modul
ar Equivalence & Reduction" }}{PARA 0 "" 0 "" {TEXT -1 344 "\nModular \+
arithmetic, or clock arithmetic, reduces all positive integers to a se
t of remainders. This is done relative to some fixed integer n. For ex
ample, lets consider numbers \"modulo 5\". This means any integer is e
quivalent to the remainder of that number divided by 5. In this contex
t, we don't care about the quotient, only the remainder.\n" }}{EXCHG
{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "17 mod 5;" }}}{EXCHG {PARA 0 "> " 0
"" {MPLTEXT 1 0 13 "irem( 17, 5);" }}}{PARA 0 "" 0 "" {TEXT -1 131 "\n
This is called \"clock arithmetic\" sometimes because it works similar
to the way a clock works - cycling through the same numbers.\n" }}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "for k from 1 to 25 do k,` mo
d 12 is `, k mod 12; od;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50
"for k from 1 to 19 do k,` mod 5 is `, k mod 5; od;" }}}{PARA 0 "" 0 "
" {TEXT -1 263 "\nYou can see that the results at right goes through t
he same 5 numbers : 0, 1, 2, 3, and 4 - like a clock with only 5 hours
( and that starts at 0 rather than 1).\n\nA regular clock shows the s
ame time 12 hours later as it does 24, 36, 48, 60, 72, ... hours later
.\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "3 mod 12;\n15 mod 12;
\n27 mod 12;\n39 mod 12;" }}}{PARA 0 "" 0 "" {TEXT -1 250 "\n Here are
the numbers from 0 to 69, mod 7. Basically its a remainder chart. For
any number in the body of the table, you can look at the top row to s
ee what its remainder would be modulo 7. All of the numbers in each co
lumn are all equivalent mod 7!" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1
0 12 "ModTable(7);" }}}{PARA 0 "" 0 "" {TEXT -1 132 "\nHere are the nu
mbers from 0 to 23, mod 4. Again, all of the numbers in each column ca
n be reduced to the remainder in the top row.\n" }}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 12 "ModTable(4);" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 13 "ModTable(13);" }}}{PARA 0 "" 0 "" {TEXT -1 2 "\n " }}
}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 3 " " }{TEXT 263 19 "2. Modular Ad
dition" }}{PARA 0 "" 0 "" {TEXT -1 128 "\nWhen adding two numbers, and
the result is less than n (the modular base), then the numbers simple
add. However, if the result\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1
0 20 "2 + 3; % = % mod 7;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0
22 "(5 + 3); % = % mod 7;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0
22 "(5 + 2); % = % mod 7;" }}}{PARA 0 "" 0 "" {TEXT -1 1 "\n" }}}
{SECT 1 {PARA 4 "" 0 "" {TEXT -1 3 " " }{TEXT 264 26 "3. Modular Add
ition Tables" }}{PARA 0 "" 0 "" {TEXT -1 67 "\nWe can make addition ta
bles modulo a number. Note that 0 + k = k.\n" }}{EXCHG {PARA 0 "> " 0
"" {MPLTEXT 1 0 15 "ModAddTable(3);" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 15 "ModAddTable(4);" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 15 "ModAddTable(5);" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 16 "ModAddTable(11);" }}}{PARA 0 "" 0 "" {TEXT -1 1 "\n"
}}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 3 " " }{TEXT 265 25 "4. Modular \+
Multiplication" }}{PARA 0 "" 0 "" {TEXT -1 84 "\nModular multiplicatio
n is simply multiplying two integers - then reduce modularly.\n" }}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "3*4; % mod 13;" }}}{EXCHG
{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "3*5; % mod 13;" }}}{EXCHG {PARA 0 "
> " 0 "" {MPLTEXT 1 0 14 "6*5; % mod 13;" }}}{PARA 0 "" 0 "" {TEXT -1
2 "\n " }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 3 " " }{TEXT 266 32 "5. \+
Modular Multiplication Tables" }}{PARA 0 "" 0 "" {TEXT -1 40 "\nWe can
make multiplication tables too.\n" }}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 16 "ModMultTable(2);" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 16 "ModMultTable(5);" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 17 "ModMultTable(11);" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 17 "ModMultTable(15);" }}}{PARA 0 "" 0 "" {TEXT -1 2 "\n \+
" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 3 " " }{TEXT 268 17 "6. Modula
r Powers" }}{PARA 0 "" 0 "" {TEXT -1 94 "\nSimilar to products, we can
find modular powers, by find the power, then reducing modularly.\n" }
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "3^2; % mod 17;" }}}{EXCHG
{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "3^3; % mod 17;" }}}{EXCHG {PARA 0 "
> " 0 "" {MPLTEXT 1 0 53 "for k from 1 to 12 do \n '3'^k = 3^k m
od 17;\nod;" }}}{PARA 0 "" 0 "" {TEXT -1 2 "\n " }}}{SECT 1 {PARA 4 "
" 0 "" {TEXT -1 3 " " }{TEXT 267 23 "7. Modular Power Tables" }}
{PARA 0 "" 0 "" {TEXT -1 128 "\nWe can easily create tables of the pow
ers. The numbers along the right column are the integers. The powers a
re in the top row.\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "ModP
owTable(3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "ModPowTable(
5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "ModPowTable(7);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "ModPowTable(12);" }}}{PARA
0 "" 0 "" {TEXT -1 2 "\n " }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 3 " \+
" }{TEXT 270 24 "8. The Order of a Number" }}{PARA 0 "" 0 "" {TEXT -1
63 "\nPlease take a moment to look for some patterns in this table.\n
" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "ModPowTable(5);" }}}
{PARA 0 "" 0 "" {TEXT -1 31 "\n\nA few observations :\n " }
{TEXT 271 1 "1" }{TEXT -1 5 ". " }{XPPEDIT 18 0 "k^1 = k" "6#/*$%\"
kG\"\"\"F%" }{TEXT -1 108 " (of course), this is why the first col
umn of the table (under 1) matches the original numbers.\n " }
{TEXT 272 4 "2. " }{TEXT -1 1 " " }{XPPEDIT 18 0 "k^p = k" "6#/)%\"kG
%\"pGF%" }{TEXT -1 169 " a bit more surprising - the last column of
the table (under 5) matches the original numbers too.\n \+
This is true modulo a prime number.\n " }{TEXT 273 7
" 3. " }{TEXT -1 1 " " }{XPPEDIT 18 0 "k^h = 1;" "6#/)%\"kG%\"hG\"
\"\"" }{TEXT -1 195 " for all non-zero numbers at some point - but \+
that point varies. The minimal exponents that give \n \+
1 are : 1, 4, 4, 2 ... all divisors of p-1 = 5-1 = 4. ( 1^1
= 1, " }{XPPEDIT 18 0 "2^4" "6#*$\"\"#\"\"%" }{TEXT -1 5 " =1, " }
{XPPEDIT 18 0 "3^4" "6#*$\"\"$\"\"%" }{TEXT -1 6 " = 1, " }{XPPEDIT
18 0 "4^2" "6#*$\"\"%\"\"#" }{TEXT -1 85 " = 1).\n\n\nThe smallest pos
itive integer h, for which k to the h is one, is called the " }{TEXT
274 5 "order" }{TEXT -1 1 " " }{TEXT 275 10 "of k mod p" }{TEXT -1 63
". We can find the order directly using a Maple command. " }}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "with(numtheory):" }}}{EXCHG
{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "order(2,5); order(4,5);" }}}{EXCHG
{PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "for k from 1 to 5 do `order of `, k
, ` is `, order(k,5); od;" }}}{PARA 0 "" 0 "" {TEXT -1 99 "5 fails bec
ause that is congruent to zero mod 5.\n\nFind the order of the numbers
1 through 6 mod 7 :" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "ModP
owTable(7);" }}}{PARA 0 "" 0 "" {TEXT -1 53 "\n\nFind the order of the
numbers 1 through 10 mod 11 :" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1
0 16 "ModPowTable(11);" }}}{PARA 0 "" 0 "" {TEXT -1 36 "\n\nWhat if n \+
is not a prime number? \n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15
"ModPowTable(6);" }}}{PARA 0 "" 0 "" {TEXT -1 529 "\nMany of the numbe
rs never become one by raising them to powers. Which numbers do have t
his property? And what distinguishes them?\n\nThe only numbers which c
an be raised to one, are 1 and 5. The numbers 2, 3, and 4 never become
one. The distinction is that 1 and 5 are relatively prime to 6, while
2, 3, and 4 have a gcd greater than one.\n\nLets look at some other e
xamples. What non-zero integers less than 8 are relatively prime to 8?
1, 3, 5, and 7. We would expect to see that these can be raised to po
wers that make them one.\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0
15 "ModPowTable(8);" }}}{PARA 0 "" 0 "" {TEXT -1 64 "\n\nFor 9, the re
latively prime numbers are 1, 2, 4, 5, 7, and 8.\n" }}{EXCHG {PARA 0 "
> " 0 "" {MPLTEXT 1 0 15 "ModPowTable(9);" }}}{PARA 0 "" 0 "" {TEXT
-1 2 "\n " }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 3 " " }{TEXT 269 25 "
9. Multiplicative Inverse" }}{PARA 0 "" 0 "" {TEXT -1 160 "\nIn the wo
rld of real numbers, every non-zero number has a multiplicative invers
e. Given a number a, there is a number b, such that ab = 1. Often we c
all b the " }{TEXT 276 10 "reciprocal" }{TEXT -1 7 " of a.\n" }}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "4 * (1/4);" }}}{EXCHG {PARA
0 "> " 0 "" {MPLTEXT 1 0 16 "(2/41) * (41/2);" }}}{EXCHG {PARA 0 "> "
0 "" {MPLTEXT 1 0 13 "(.0125) * 80;" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 14 "-31 * (-1/31);" }}}{PARA 0 "" 0 "" {TEXT -1 315 "\nIn
the modular world, we don't have fractions so this is not possible. H
owever, under what conditions are there other integers which serve the
same purpose as being multiplicative inverses?\n\nFor example, take t
he number 3, mod 7. Is there an integer such at 3*b = 1 (mod 7)? Yes, \+
5 is the \"reciprocal of 3 mod 7\",\n" }}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 2 "3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "3*5 ;
% = % mod 7;" }}}{PARA 0 "" 0 "" {TEXT -1 100 "\nHow can we better und
erstand this process? A quick consideration of the numbers mod 7 once \+
again :" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "ModPowTable(7);
" }}}{PARA 0 "" 0 "" {TEXT -1 186 "\n\nSince n = 7 is prime, every non
-zero number 1,2, 3, 4, 5, 6 has an order - an exponent h, such that k
^h = 1. This leads to an interesting idea. Given any such number k, mu
ltiplying by " }{XPPEDIT 18 0 "k^(h-1)" "6#)%\"kG,&%\"hG\"\"\"F'!\"\"
" }{TEXT -1 9 " gives " }{XPPEDIT 18 0 "k * k^(h-1) = k^h " "6#/*&%
\"kG\"\"\")F%,&%\"hGF&F&!\"\"F&)F%F)" }{TEXT -1 58 "= 1.\n\nUsing this
idea we can find the inverse for 3 mod 7." }}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 17 "h := order(3, 7);" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 17 "3^(h-1);\n% mod 7;" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 14 "3*5; \n% mod 7;" }}}{PARA 0 "" 0 "" {TEXT -1 34 "\n\n
Find the reciprocal of 5 mod 11." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT
1 0 19 "h := order( 5, 11);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0
18 "5^(h-1); % mod 11;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "5
*9; % mod 11;" }}}{PARA 0 "" 0 "" {TEXT -1 34 "\n\nFind the reciprocal
of 8 mod 17." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "h := order(
10, 17);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "10^(h-1); % mo
d 17;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "10*12; % mod 17;"
}}}{PARA 0 "" 0 "" {TEXT -1 152 "\nWhen n is not prime, not every numb
er has an inverse. However, those numbers relatively prime to the modu
lar base do.\n Find the reciprocal of 8 mod 17." }}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 19 "h := order( 8, 15);" }}}{EXCHG {PARA 0 "> " 0
"" {MPLTEXT 1 0 18 "8^(h-1); % mod 15;" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 14 "8*2; % mod 15;" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1
3 " " }{TEXT 261 22 "10. Quadratic Residues" }}{PARA 0 "" 0 ""
{TEXT -1 75 "\nJust looking at the squares of integers mod 5, what is \+
the set of values?\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "ModP
owTable(5);" }}}{PARA 0 "" 0 "" {TEXT -1 251 "\nThe only non-zero squa
res are 1 and 4. These are called the quadratic residues - what is lef
t after the multiples of 5 are boiled off, so to speak. \n\nOnly these
numbers have modular square roots. For example there are two solution
s to the equation :\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "x^2 \+
= 4;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "2^2 mod 5; 3^2 mod \+
5;" }}}{PARA 0 "" 0 "" {TEXT -1 46 "\nSo the square roots of 4 mod 5 a
re 2 and 3.\n\n" }}{PARA 0 "" 0 "" {TEXT -1 39 "What are the quadratic
residues mod 7?\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "ModPow
Table(7);" }}}{PARA 0 "" 0 "" {TEXT -1 135 "\nThe residues mod 7 are \+
1, 2 and 4. What are the square roots of 2?\n\nThe residues mod 9 are \+
1, 4, 7. What are the square roots of 7?\n" }}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 15 "ModPowTable(9);" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 2 "\n " }}}{PARA 0 "" 0
"" {TEXT 259 73 "\n \251 2002 Waterloo Maple Inc & Gregory Moo
re, all rights reserved." }}}{MARK "5" 0 }{VIEWOPTS 1 1 0 1 1 1803 1
1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }