# More than one modular multiplicative inverse possible?

I am redoing exams as a preparation and I found this weird particular exercise to me.

"Does $32$ have a multiplicative inverse in modulo $77$? If yes, calculate the inverse."

Since the $\gcd(77,32)$ is $1$, it has an inverse. However, when I calculated it using the extended euclidean algorithm, I ended up with

$1 = (-12)32 + (5)77$, which means my inverse of $32$ in mod $77$ is $-12$? When I used an online calculator to check my answer I always got $65$, though.

I'm not quite sure I understand why or how it is $65$ and not $-12$... I have redone my method multiple times but I always end up with $-12$

$$-12 \equiv 65 \pmod{77}$$

To see that notice that $65-(-12)=77$.

• Wow, thank you so much! How did I not see or think of this... pure embarrassment haha! – Disjoint Jan 28 '18 at 18:57
• we all make mistake, no worries. – Siong Thye Goh Jan 28 '18 at 18:58

Are you sure that $65$ and $-12$ are different?

Think about how integers "name" integers mod $k$: every integer $n$ corresponds to the set $\{m: m=n$ (mod $k)\}$ of integers which are equivalent to it mod $k$. Two different integers can correspond to the same set; for example, $1$ and $3$ represent the same thing in mod $2$.

The right way to think about this, in my opinion, is the following. "The integers mod $k$" is really a structure in its own right, usually denoted "$\mathbb{Z}/k\mathbb{Z}$" - elements of this structure aren't integers, but rather sets of integers. For instance, $\mathbb{Z}/2\mathbb{Z}$ (integers mod $2$) has two elements, "even numbers" and "odd numbers."

Specifically, elements of $\mathbb{Z}/k\mathbb{Z}$ are equivalence classes. When we say "$x=y$ (mod $k)$," what we really mean is that the equivalence class "$x$ (mod $k$)" is the same as the equivalence class "$y$ (mod $k$)," and the point in this particular question is that $65=-12$ (mod $77)$.