# Proving Bezouts identity is equal to the modular multiplicative inverse

I cant seem to figure out how the modular multiplicative inverse is actually equal to Bezouts identity. More specifically, im interested in the case when $\gcd(e,\phi(n)) = 1$. This is what i do understand thus far, \begin{align} &\text{Let a }= e ,\quad b = \phi(n) \text{ and choose e, $\phi(n)$ to be relatively prime then,}\\ &\rightarrow ax + by =\gcd(a,b) \qquad \text{(Bezouts Identity)}\\ &\rightarrow ex + \phi(n)y =\gcd(e,\phi(n))\\ &\rightarrow ex + \phi(n)y \equiv ex \pmod{\phi(n)}\\ &\vdots\\ &\rightarrow ex\equiv1\pmod{\phi(n)} \end{align} Im actually confused right at step three. I dont understand at all why we are able to right it this way. I believe that if we mod the left side by $y\phi(n)$ then the $y\phi(n)$ will just be equal to $0$ since, $$\phi(n)y \equiv ex \pmod{\phi(n)} \\ \rightarrow \phi(n)\text{ } |\text{ } \phi(n)y - ex.$$ If this is true that would then bring us to $$ex \equiv ex \pmod{\phi(n)}.$$

So can someone please fill in the blanks here with a short explanantion of why in each step starting at the third $\rightarrow$.

• Isn't that just by considering once the left hand side of the 2nd step which is actually congruent to $de$ since you're adding a multiple of $\phi(n)$ and then substituting 1 in the right hand side, by assumption ; and then equaling them together $\mod \phi(n)$ ? So you just take the 2nd step and consider its congruency $\mod \phi(n)$, this brings you directly to step 4.
– Lery
Nov 23, 2015 at 18:38
• Yes, I believe that makes sense, however im still a little confused. Nov 23, 2015 at 18:46

Here, as you have considered $(e,\phi(n))=1$, you will have $ex+\phi(n)y=1$(from Bezouts identity). Now, if you take $\pmod{\phi(n)}$, you will directly get, $ex\equiv 1\pmod{\phi(n)}$.
It is not true that, $$y\phi(n)\equiv ex\pmod{\phi(n)}$$
So, the steps will be: $$ex+\phi(n)y=\gcd(e,\phi(n))=1,~\text{as you have considered them to be coprime}\\ex+\phi(n)y\equiv ex\pmod{\phi(n)}\equiv 1\pmod{\phi(n)},\text{(taking modulo both side)}\\ex\equiv 1\pmod{\phi(n)}$$