# Why does this trick to find the inverse of an element in a Multiplicative Cyclic Group work?

Take a Multiplicative group G, defined by a prime p. Now take an element t from it. Its inverse is t-1. To calculate the inverse you can use the extended Euclidian algorithm or this trick, which I found on wikipedia:

t-1 = tp-2 mod p

Now this makes some sense to me, but the following, which I found in some code, does not.

Take t, and raise it to u (also in G): tu

(tu)-1 = tp-1-u mod p

What is this trick called, and why does it work?

-
Fermat's Little Theorem. – HJRW Nov 9 '10 at 21:48

The "trick" is that $\displaystyle t^{p-1} = 1 \mod p$ always.

So $\displaystyle t^{p-1-u} \cdot t^u = 1 \mod p$ and

so

$\displaystyle t^u$ and $\displaystyle t^{p-1-u}$ are inverses.

Also for a general group $G$ and $a, b \in G$, $a^b$ does not make much sense as a power of $a$.

As Arturo points out, it in fact is used to denote the element $b^{-1}ab$.

-
unfortunately, it does make sense for a general group, but it means something completely different. (The standard meaning of $x^y$ for $x$ and $y$ in an arbitrary group is $x^y = y^{-1}xy$...) – Arturo Magidin Nov 9 '10 at 21:54
@Arturo: I meant that as taking a to the power of b. (Please read the question, there seems to be some confusion in OP's mind in that regard). – Aryabhata Nov 9 '10 at 21:57
Thanks guys, not sure why that eluded me so much. – Tom Ritter Nov 9 '10 at 21:59
yes, I agree; I was just pointing out that it is unfortunate that the notation actually has a meaning, which has nothing to do with what the OP was trying to do/think about. (And in an abelian group, like this is, it really amounts to nothing...) – Arturo Magidin Nov 9 '10 at 22:01
@Tom: You are welcome. – Aryabhata Nov 9 '10 at 22:51

HINT $\rm\displaystyle\quad\quad A^N = 1\ \ \Rightarrow\ \ A^{-K}\ =\ \frac{1}{A^K}\ =\ \frac{A^N}{A^K}\ =\ A^{N-K}$

It's not really a "trick" nor does it have any standard name. It's simply a consequence of the cyclic structure, viz $\rm\ -K \ \equiv\ N-K\ \:(mod\ N)\:$. This is already quite familiar to everyone in the form of clock arithmetic, e.g. 1:50 = 10 before 2,$\$ i.e. $\rm\: -10\ \equiv\ 50\ \ (mod\ 60)\:.\:$ Note that, as a consequence, there can be no concept of sign (positive/negative) in cyclic groups, i.e. they cannot be ordered.

-