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.

The following message was encoded with an affine matrix cipher. The vectors were of length 2. The alphabet was: upper case letters, followed by a space, followed by the lower case letters. The message starts: ``Why did''. Decode the message.

$$\mbox{iXazjeaeiuafiddjflaosdtpatiuafpseb}$$

3.

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)$.

4.

The function $\phi$ has the following properties: if p is a 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$.