3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The "group" is $\mathbb{Z}_{27}^{\ast}$? $\endgroup$ – Corrêa Mar 1 '18 at 7:28
  • $\begingroup$ 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. $\endgroup$ – Chuck Mar 1 '18 at 7:34
  • 1
    $\begingroup$ What makes you think that $-10$ is not a representative of an element of the group? $\endgroup$ – Hagen von Eitzen Mar 1 '18 at 7:35
  • $\begingroup$ 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? $\endgroup$ – Chuck Mar 1 '18 at 7:38
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Jyrki Lahtonen Mar 1 '18 at 7:40
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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