# Finding inverse in multiplicative group

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

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

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

= -5*27 + 17*8

• The "group" is $\mathbb{Z}_{27}^{\ast}$? – Corrêa Mar 1 '18 at 7:28
• Yes. I think the edit I made gives a pretty good and simple arithmetic reason but maybe there is some more interesting fundamental reason that it works out. – Chuck Mar 1 '18 at 7:34
• What makes you think that $-10$ is not a representative of an element of the group? – Hagen von Eitzen Mar 1 '18 at 7:35
• Not sure, just doing really simple groups as part of a separate class so we did not really do any detail. I'm guessing that the group of integers mod 27 should only contain numbers between 0 and 26? – Chuck Mar 1 '18 at 7:38
• The elements of $\Bbb{Z}_{27}^*$ are not integers. They are residue classes of integers (also called cosets). The residue class of $-10$ is the answer. For some purposes it is convenient to use the residue class of $17$ instead, but it is the same element (=the same residue class) because $17\equiv-10\pmod{27}$. – Jyrki Lahtonen Mar 1 '18 at 7:40

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