Problems of the day

1.

Claim: if p is a prime number, then $a^p = a (\mbox{mod } p)$ for any integer a. Use Maple to check this for the first ten prime numbers

2.

For n a positive integer, let $\phi(n)$ denote the number of integers a with 0 < a < n for which $\mathop{\rm gcd}(a,n) = 1$. For example, $\phi(3) = 2$ (a=1 and a=2 have $\mathop{\rm gcd}(a,3) = 1$). Write a Maple routine to calculate $\phi(n)$. Calculate $\phi(1)$, ..., $\phi(10)$.

3.

The function $\phi$ has the following properties: if p is prime then $\phi(p) = p - 1$; if m and n are relatively prime (mand n positive integers) then $\phi(mn) = \phi(m)\phi(n)$. Use these to check your implementation of the function $\phi$.

4.

Maple has the Euler phi function built in: it is called ``phi'' and is in the numtheory library. About how long does it take Maple to find phi of an integer with about 30 digits?