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$
0

3 Answers 3

4
$\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$
3
$\begingroup$

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

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

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

The multiplicative inverse should be a positive integer. You are correct that $$-12 * 32 \pmod{77} = 1.$$ But $65 * 32 \pmod{77} = 1$ as well. If you come up with a negative multiplicative inverse, then you need to take

$$\text{negative multiplicative inverse}\pmod{77} \,=\,\, \text{ positive multiplicative inverse}.$$

By all means verify this for yourself. Test that both function as multiplicative inverses. But for the test, only the positive one is correct.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.