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.

The following pages link to this page.