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