Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
Fermat's Little Theorem. –  HJRW Nov 9 '10 at 21:48

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
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$...) –  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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.