Computing Multiplicative Inverses For Small N

Please Login to access more options.

Problem 28 (Computing Multiplicative Inverses For Small N)

To use modular arithmetic in matrix encryption, we must be able to find the modular multiplicative inverse of $a \mod n$. For each $n\leq 13$ and $a\in \mathbb{Z}_n$, we now compute the inverse of $a\mod n$ or explain why it does not have one.

1. Why does $0\mod n$ never have an inverse?
2. What is the multiplicative inverse of $1\mod n$?
3. For $n=3$, what is the multiplicative inverse of $a=2$.
4. For $n=4$, show that 2 does not have an inverse by computing $2\cdot 0$, $2\cdot 1$, $2\cdot 2$, and $2\cdot 3$ all modulo $4$. What is $3^{-1}\mod 4$?
5. For each $n$ between 5 and 13, create a table that shows the inverse of each $a\in \mathbb{Z}_n$. List the elements of $\mathbb{Z}_n$ along the top row, and beneath each element list the multiplicative inverse, or cross off the number if there is no multiplicative inverse.

When you are done you should have a list of the elements of $U(n)$ for each $n$ up to 13, as well as the inverse of each element in $U(n)$. Do you see any patterns?

For $n=9$, you should obtain a table somewhat similar to the following table.

The following pages link to this page.