Find the inverse of $8$ modulo $27$

Question

I'm working on finding the inverse of an element in a multiplicative group (mod n). Say the question is:

Find x such that 8x = 1 (mod 27)

Applying extended Euclid's algorithm gives: 1 = 3*27 - 10*8

So x = -10 satisfies the equation, however I would like to have an x which is also in the group. What I did (for no particular reason) is try -10 mod 27 and for some reason it works:

8*17 = 1 mod 27

But why?

-- Edit --

Actually I think I figured it out:

Take 1 = 3*27 - 10*8

Add and subtract 27*8:

1 = 3*27 - 10*8 + 27*8 - 27*8

= 3*27 + 17*8 - 8*27

= -5*27 + 17*8

Answer 1

Interpret your congruences computations as computations in the ring $\mathbf Z/27\mathbf Z$. Determining the modular inverse of $8$ is finding the inverse of $[8]$ (the congruence class of $8$ mod. $27$).

In this ring, the extended Euclidean algorithm tells you that $[8]^{-1}=[-10]$. But $$[-10]=\{-10,-10+27=\color{red}{17}, 44,71,\dots,-10-27=-37, -64, -91,\dots \}.$$ So, whatever solution the extended Euclidean algorithm provides, there will exactly one representative of the same class between $1$ and $26$.

Answer 2

Remember that $a \in \mathbb{Z}_{n}$ is invertible if, and only if, $\gcd(a,n)=1$. But, $\gcd(9,27) = 9$ so, $9$ is not invertible. Therefore, $\mathbb{Z}_{27}^{\ast}$ is not a group.

But, $\gcd(8,27) = 1$, so $8$ is invertible. You found it correctly.