# Why are these two equivalent? (Modular multiplicative inverse)

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

• Multiply by $e$ both sides – user32847 Mar 21 '13 at 23:00
• What do you think $e^{-1}$ means? – anon Mar 22 '13 at 4:02

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

• 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
• :-) ${}{}{}{}{}{}$ – mrs Mar 22 '13 at 19:50
• @amWhy: well, here is upvote back! :-) – Amzoti May 14 '13 at 1:46

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

• 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
• 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
• @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
• 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

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