0
$\begingroup$

I am trying to solve an RSA problem. In order to calculate $d$, I have to calculate $d$ with $e=3$ and $$d\cdot e\equiv1 \pmod{40}$$ Obviously the answer is $d=27$, but I want to solve this with the extended Euclidean algorithm.
Though I know how this works, I am stuck because in the first step of the algorithm I get $$40=3\cdot13+1$$

The remainder is 1 and the algorithm stops there. How do I get $d=27$ by using the extended Euclidean algorithm?

I dont have a problem solving other similar examples that dont stop in the first step. But here, because it stops in the first step of the algorithm, I get confused.

$\endgroup$

marked as duplicate by kelalaka, Ilmari Karonen, Maeher, Squeamish Ossifrage, Maarten Bodewes Mar 12 at 10:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

First, 40 = 3*13 + 1

So, we have found 1 in the first step. Then I can write 1 as following:

1 = 40 - 3*13 and this is equivalent to

1 = 40 - 13*3. 40 is equivalent to 0 mod40.

1 = -13*3. Here we get the inverse of 3 as -13 which is equivalent to 27.

$\endgroup$

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