{VERSION 2 3 "SUN SPARC UNIX" "2.3" }
{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 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 
0 0 1 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 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 
261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 0 
0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 
0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 
269 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 
0 0 1 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 }{CSTYLE "" -1 272 "" 0 1 0 0 0 0 0 1 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 }{CSTYLE "" -1 274 "" 0 1 0 0 0 
0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 
0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 
277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 0 1 0 0 0 
0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 
0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 
282 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 0 1 0 0 0 
0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 
0 }{CSTYLE "" -1 285 "" 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 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 -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 14 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 14 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 262 1 {CSTYLE "" -1 -1 "" 1 14 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 266 1 {CSTYLE "" -1 -1 "" 1 14 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 8 "1. Claim" }{TEXT -1 5 ":
 if " }{TEXT 257 1 "p" }{TEXT -1 25 " is a prime number, then " }
{TEXT 258 15 "a^p = a (mod p)" }{TEXT -1 17 " for any integer " }
{TEXT 259 1 "a" }{TEXT -1 58 ".\nUse Maple to check this for the first
 ten prime numbers." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "resta
rt;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "check := (a,p) -> a^
p mod p = a mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&checkG:6$%\"a
G%\"pG6\"6$%)operatorG%&arrowGF)/-%$modG6$)9$9%F3-F/6$F2F3F)F)" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "check (3,5);" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6#/\"\"$F$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 113 "test := proc (p)\n  local a;\n  for a from 1 to p-1 do\n    if \+
(not (check (a,p))) then print (a, p); fi;\n  od;\nend:" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "test (5);" }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 9 "test (6);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"#
\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"&\"\"'" }}}{EXCHG {PARA 
257 "" 0 "" {TEXT -1 7 "2. For " }{TEXT 260 1 "n" }{TEXT -1 25 " a pos
itive integer, let " }{TEXT 261 6 "phi(n)" }{TEXT -1 31 " denote the n
umber of integers " }{TEXT 262 1 "a" }{TEXT -1 6 " with " }{TEXT 263 
8 "0 < a < " }{TEXT -1 12 "n for\nwhich " }{TEXT 264 12 "gcd(a,n) = 1
" }{TEXT -1 37 ". Write a Maple routine to calculate " }{TEXT 269 6 "p
hi(n)" }{TEXT -1 13 ".  Calculate " }{TEXT 270 6 "phi(1)" }{TEXT -1 7 
", ..., " }{TEXT 271 7 "phi(10)" }{TEXT -1 1 "." }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 54 "check := (a,n) -> if (gcd (a,n)=1) then 1; else 0; fi;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&checkG:6$%\"aG%\"nG6\"6$%)operatorG
%&arrowGF)@%/-%$gcdG6$9$9%\"\"\"F4\"\"!F)F)" }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 12 "check (3,5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"
\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "check (3,6);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 40 "phi := n -> add (check (a,n), a=1..n-1);" }}{PARA 7 "
" 1 "" {TEXT -1 42 "Warning, `a` in call to `add` is not local" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$phiG:6#%\"nG6\"6$%)operatorG%&arrow
GF(-%$addG6$-%&checkG6$%\"aG9$/F2;\"\"\",&F3F6!\"\"F6F(F(" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "seq (phi (n), n = 1..10);" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6,\"\"!\"\"\"\"\"#F%\"\"%F%\"\"'F&F'F&" }}}
{EXCHG {PARA 262 "" 0 "" {TEXT -1 16 "3. The function " }{TEXT 272 3 "
phi" }{TEXT -1 34 " has the following properties: if " }{TEXT 273 1 "p
" }{TEXT -1 15 " is prime then " }{TEXT 274 14 "phi(p) = p - 1" }
{TEXT -1 5 "; if " }{TEXT 275 1 "m" }{TEXT -1 5 " and " }{TEXT 276 1 "
n" }{TEXT -1 23 " are\nrelatively prime (" }{TEXT 277 1 "m" }{TEXT -1 
5 " and " }{TEXT 278 1 "n" }{TEXT -1 25 " positive integers) then " }
{TEXT 279 23 "phi(mn) = phi(m) phi(n)" }{TEXT -1 58 ".  Use these to c
heck your\nimplementation of the function " }{TEXT 281 3 "phi" }{TEXT 
-1 1 "." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "seq (phi(ithprim
e(i)) - (ithprime (i) - 1), i=1..20);" }}{PARA 11 "" 1 "" {XPPMATH 20 
"66\"\"!F#F#F#F#F#F#F#F#F#F#F#F#F#F#F#F#F#F#F#" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 83 "seq (phi(ithprime(i)*ithprime(i+1)) - phi(ithp
rime(i))*phi(ithprime(i+1)), i=1..5);" }}{PARA 11 "" 1 "" {XPPMATH 20 
"6'\"\"!F#F#F#F#" }}}{EXCHG {PARA 266 "" 0 "" {TEXT -1 23 "4. Maple ha
s the Euler " }{TEXT 282 3 "phi" }{TEXT -1 33 " function built in: it \+
is called " }{TEXT 283 3 "phi" }{TEXT -1 77 " and is in the numtheory \+
library.  About how\nlong does it take Maple to find " }{TEXT 284 3 "p
hi" }{TEXT -1 26 " of an integer with about " }{TEXT 285 2 "30" }
{TEXT -1 8 " digits?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "rest
art;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "with (numtheory):" 
}}{PARA 7 "" 1 "" {TEXT -1 33 "Warning, new definition for order" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "time(phi(1234567890123456789
01234567890));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"$4*!\"$" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "time(phi(3837492302132983850
48529564783));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"&q;%!\"$" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "21 0 0" 0 }
{VIEWOPTS 1 1 0 1 1 1803 }