Please Login to access more options.
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.
- Why does $0\mod n$ never have an inverse?
- What is the multiplicative inverse of $1\mod n$?
- For $n=3$, what is the multiplicative inverse of $a=2$.
- 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$?
- 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.
| $a$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| $a^{-1}$ | x | 1 | 5 | x | 7 | 2 | x | 4 | 8 |
Solution
1. We claim $0\mod{n}$ never has an inverse (except in the case of $n=1$). Pick $n\geq 2$. Suppose by way of contradiction that $b$ is a multiplicative inverse $\mod{n}$. Thus we know $0(b)\mod{n}=1$, but $0$ multiplied by any number is 0, thus it must be that $0(b)\mod{n}=0\mod{n}=0$, a contradiction. Thus, for all $n\geq 2$ we have that $0\mod{n}$ has no multiplicative inverse.
2. We claim the multiplicative inverse of $1\mod{n}$ is 1. Pick $n\geq 2$. We compute $1(1)\mod{n}=1\mod{n}=1$. Thus, the multiplicative inverse of $1\mod{n}$ is 1.
3. Let $n=3$. The multiplicative inverse of $a=2$ is $b=2$ because $ab\mod{3}=2(2)\mod{3}=4\mod{3}=1$.
4. Let $n=4$. We claim 2 does not have a multiplicative inverse. We consider each case. The results are summarized in the table below.
$$\begin{array}{c|c|c}
a&2(a)&2(a)\mod{4}\\ \hline
0&0&0\\
1&2&2\\
2&4&0\\
3&6&2
\end{array}$$
Thus, because there is not a $b\in\mathbb{Z}_4$ such that $2b\mod{4}=1$, we know that 2 does not have a multiplicative inverse.
5. The tables below show the numbers $a$ that have multiplicative inverses $a^{-1}$ for $a\mod{n}$.
| $n=5$ | $a$ | 0 | 1 | 2 | 3 | 4 |
| | $a^{-1}$ | X | 1 | 3 | 2 | 4 |
| $n=6$ | $a$ | 0 | 1 | 2 | 3 | 4 | 5 |
| | $a^{-1}$ | X | 1 | X | X | X | 5 |
| $n=7$ | $a$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| | $a^{-1}$ | X | 1 | 4 | 5 | 2 | 3 | 6 |
| $n=8$ | $a$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| | $a^{-1}$ | X | 1 | X | 3 | X | 5 | X | 7 |
| $n=9$ | $a$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| | $a^{-1}$ | X | 1 | 5 | X | 7 | 2 | X | 4 | 8 |
| $n=10$ | $a$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| | $a^{-1}$ | X | 1 | X | 7 | X | X | X | 3 | X | 9 |
| $n=11$ | $a$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| | $a^{-1}$ | X | 1 | 6 | 4 | 3 | 9 | 2 | 8 | 7 | 5 | 10 |
| $n=12$ | $a$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| | $a^{-1}$ | X | 1 | X | X | X | 5 | X | 7 | X | X | X | 11 |
| $n=13$ | $a$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| | $a^{-1}$ | X | 1 | 7 | 9 | 10 | 8 | 11 | 2 | 5 | 3 | 4 | 6 | 12 |
Tags
- Week4 - Which week are you writing this problem for?
- Levi - Sign your name by just changing "YourName" to your wiki name.
- Complete
- When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
- If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
- I'll mark your work with [[!Complete]] after you have made appropriate revisions.
