2
$\begingroup$

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?

  • 5
    Fermat's Little Theorem.2010-11-09

2 Answers 2

7

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

  • 1
    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$...)2010-11-09
  • 0
    @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).2010-11-09
  • 0
    Thanks guys, not sure why that eluded me so much.2010-11-09
  • 0
    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...)2010-11-09
  • 0
    @Tom: You are welcome.2010-11-09
2

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.