0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Lery Nov 23 '15 at 18:38
  • $\begingroup$ Yes, I believe that makes sense, however im still a little confused. $\endgroup$ – After_Sunset Nov 23 '15 at 18:46
0
$\begingroup$

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)}$$

I think it is clear now, please feel free to ask in case you have any query about this explanation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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