0
$\begingroup$

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$

Thank you for your time in advance.

$\endgroup$
2
$\begingroup$

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

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

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

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.