Please Login to access more options.

Problem 34 (When Does An Integer Have A Modular Multiplicative Inverse)

Let $a$ and $n$ be integers, with $n>1$. Show that the following are equivalent.

  1. The integer $a$ has a multiplicative inverse mod $n$
  2. We have $1\in \text{span}(a,n)$. In other words, we can write 1 as a linear combination of $a$ and $n$.
  3. We have $\text{span}(a,n)=\mathbb{Z}$. Remember that $\text{span}(a,n) = \{sa+tn\mid s,t\in\mathbb{Z}\}.$

Remember, to show that three things are equivalent you must show that each implies the other. One way to do this is show that 1 implies 2, then show that 2 implies 3, and then show that 3 implies 1. Then each implies the other.

Solution

We will show that statements (1), (2), and (3) are each equivalent by showing that $(1) \implies (2) \implies (3) \implies (1)$.

Let $a^{-1} a (mod\; n) = 1$. In terms of the division algorithm this means $$ \begin{align} a^{-1} a = q n + 1 &\Longleftrightarrow a^{-1} a - q n = 1 \\ &\Longleftrightarrow a^{-1} a + (- q) n = 1 \end{align} $$ The last statement above shows that we can write $1$ in terms of an integer linear combination of integers, with coefficients $a^{-1}, q \in \mathbb{Z}$. Thus we have $1 \in span(a, n)$, showing that (1) implies (2).

Let $1 \in span(a, n)$. From problem thirty-three it follows that for every $b \in \mathbb{Z}$ we have $b = b \cdot 1 \in span(a, n)$. Therefore $\mathbb{Z} \subseteq span(a, n)$. Similarly let $c \in span(a, b)$. This means that $c$ may be written as an integer linear combination of $a$ and $n$. Since $c$ is the sum of integers it follows that $c \in \mathbb{Z}$. Therefore $span(a, n) \subseteq \mathbb{Z}$. Thus we have that $span(a, n) = \mathbb{Z}$, showing that (2) implies (3).

Let $span(a, n) = \mathbb{Z}$. It follows that $1 \in span(a, n)$, which means that $1$ may be written as an integer linear combination of $a$ and $n$, namely $1 = s a + t n$ for some $s, t \in \mathbb{Z}$. This statement may be rewritten as $1 + (-t) n = s a$ which, in light of the division algorithm, implies that $n$ divides $s a$ with a remainder of $1$. This means that $1 = s a\; (mod\; n)$, implying that $s = a^{-1}(mod\; n)$.

To verify that this is the case we compute $$ \begin{align} a^{-1} \cdot a (mod\; n) = 1 \nonumber &\Longleftrightarrow a^{-1}(mod\; n) \cdot a (mod\; n) = 1 \\ &\Longleftrightarrow s \cdot a (mod\; n) = 1, \end{align} $$ showing that (3) implies (1).

Q.E.D.

Tags
  • Week4 - Which week are you writing this problem for?
  • Tyler - Sign your name by just changing "YourName" to your wiki name.
  • Submit
  • 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.