Assignment 8 (pdf)

True/False questions, not to turn in:

$\phi(n)$ is always strictly less than $n$, when $n\geq 2$.
If $a$, $b$ are reduced residues modulo $n$, then so is $a+b$.
If $a$, $b$ are reduced residues modulo $n$, then so is $ab$.
If $a$ is a reduced residue modulo $n$, and $m|n$, then $a$ is also a reduced residue modulo $m$.
The multiplicative inverse of an element $a$ modulo a prime $p$ is a power of the element.
$\phi(n)$ is always an even number.
$\phi(n)$ is always divisible by $4$.
There are $n>2$ and $a$ such that the multiplicative inverse of $a$ modulo $n$ is equal to $-a(=n-a)$.

Questions to turn in:

Using the formulas we have learned for $\phi$, compute $\phi(215)$. Also determine at least 5 elements that are reduced residues modulo $215$.
Using Euler's theorem followed by fast exponentiation, compute $11^{214563}\bmod 215$. Only use your calculator for computing the product of two numbers and for reducing numbers modulo another (i.e. don't just give something like $11^{313} to the calculator --- exponent made up for illustrative purposes).
Use some of the work from problem 2 to find the multiplicative inverse of $11$ modulo $215$.
Find all reduced residues in $\mathbb{Z}_{16}$, and for each residue find the first power that equals $1$. Determine if there is a reduced residue, such that looking at its powers produces all the other reduced residues.
Do the same for $\mathbb{Z}_{18}$.