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.

According to Wikipedia's entry "Modular Multiplicative Inverse," $d\equiv e^{-1} \pmod {\phi(n)}$ and $ed\equiv 1 \pmod{\phi(n)}$ are equivalent. Why is this the case? Can someone provide a step-by-step explanation as to how you can go from the first expression to the second? (I'm just starting to learn modulos to understand RSA, please keep it at a beginner level).

share|improve this question
1  
Multiply by $e$ both sides –  user32847 Mar 21 '13 at 23:00
1  
What do you think $e^{-1}$ means? –  anon Mar 22 '13 at 4:02
add comment

3 Answers 3

$$ \begin{align} d & \equiv e^{-1} \pmod {\phi(n)} \\ \\ ed & \equiv ee^{-1} \pmod{\phi(n)} \\ \\ ed & \equiv 1 \pmod{\phi(n)} \end{align} $$

$e^{-1} \pmod{\phi(n)}$ denotes (and presumes the existence of) the multiplicative inverse of the element, $e \pmod {\phi(n)},\;$; and (assuming it exists), the multiplicative inverse of $\,e\,$ is denoted $e^{-1}$.

By definition, $e^{-1}$ exists and is the multiplicative inverse of $\,e\,$ if and only if satisfies $$ee^{-1} \equiv e^{-1}e \equiv 1 \pmod{\phi(n)}$$ where $1$ denotes the multiplicative identity.

share|improve this answer
    
Lol why did someone down vote this correct answer? –  sxd Mar 21 '13 at 23:07
    
This answer assumes that if $a\equiv b\mod p$ then $ac\equiv bc\mod p$. That bears proving. (I don't know why it was down-voted though.) –  Michael Hardy Mar 21 '13 at 23:07
    
This really doesn't deserves a downvote... –  user32847 Mar 21 '13 at 23:09
    
:-) ${}{}{}{}{}{}$ –  B. S. Mar 22 '13 at 19:50
    
@amWhy: well, here is upvote back! :-) –  Amzoti May 14 '13 at 1:46
add comment

That's what "$e^{-1}$" means.

The number (or equivalence class of numbers) called $e^{-1}$ is by definition that which when multiplied by $e$ gives $1$.

For example, $2\cdot6\equiv1\mod{11}$; therefore $2=6^{-1}$ in the field of integers modulo $11$.

Later note: Since the issue was raised in comments: For some values of $n$ and $e$, the number $e$ has no mod-$n$ multiplicative inverse. That doesn't alter the validity of what I wrote above. In those cases in which there exists a number $d$ such that $ed\equiv1\pmod n$, the number $d$ is called $e^{-1}$.

Of course, for all this to make sense, it must have been shown that multiplication actually exists in this context, i.e. if $a_1\equiv a_2$ and $b_1\equiv b_2$, then $a_1b_1\equiv a_2b_2$.

share|improve this answer
    
Someone rather abruptly downvoted two answers here. Could that person explain why? My answer is the same as that of "Billy" except that "Billy"'s uses more words to say it. –  Michael Hardy Mar 21 '13 at 23:09
1  
The downvotes were mine. They were answers that I would have found very unhelpful when I was a complete beginner at modular arithmetic. "That's what $e^{-1}$ means" does not explain why a number with this property exists, or why you can do things like multiply both sides of a congruence by $e$. If the OP already knew these facts, I'm sure (s)he would have had no problem multiplying one equation by $e$ or $e^{-1}$ to get the other. –  Billy Mar 21 '13 at 23:19
2  
@Billy : One need not explain why it exists, since in some cases it doesn't. The notation $e^{-1}$ refers to a number having a certain property. There is no claim that in every case it exists. Later one might learn that if $n$ is prime then multiplicative inverses exist for everything except $0$, and if $p$ is composite then nonzero numbers without multiplicative inverses exist. But that doesn't change the fact that in those cases where an inverse of $e$ exists, the notation $e^{-1}$ simple is the name of that object, and the desired equality follows. –  Michael Hardy Mar 21 '13 at 23:21
1  
I never said that your answer was wrong. I only said it was unhelpful. The OP asked "why?", and you said "that's just what it means". That's not mathematics. In any case, I wouldn't have learnt anything from your comment when I was a beginner at modular arithmetic, so I downvoted it. Isn't that how this site works? –  Billy Mar 21 '13 at 23:31
    
My answer addressed the question directly and explained that there's nothing to prove here. And there isn't. The question itself is fully answered by saying something is a definition. –  Michael Hardy Mar 22 '13 at 16:17
add comment

The number $e^{-1}$ (defined specifically modulo $\varphi(n)$) is an integer $f$ such that $ef \equiv 1 \mod \varphi(n)$, i.e. $ef = 1 + k\varphi(n)$ for some $k$. (It might help you to computer $5^{-1} \mod 7$ or something. You should get many answers, and they should all be integers. There should only be one answer between $0$ and $6$ - what is it?)

Your two statements, written in "non-modular" arithmetic, are:

(a) $d = f + \ell\varphi(n)$ for some $\ell$

(b) $ed = 1 + m\varphi(n)$ for some $m$.

To prove that (a) implies (b), try multiplying both sides by $e$. To prove that (b) implies (a), try multiplying both sides by $f$.

share|improve this answer
add comment

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.