Suppose your RSA modulus is $55 = 5 * 11$ and your encryption exponent is $e = 3$.
Find the decryption modulus d.
I know $d = 40-13 = 27$
However, I get $1$.
$$40 = (P_1-1)(P_2-1)$$
extended euclidean algorithm:
$$40 = 3(13)+1 $$
$$1 = 40(1) + 3(-13)$$
From what I understand $d = 1$.
What am I doing wrong?
Thanks.
The extended Euclidean algorithm computation looks fine. You're just looking at the wrong number in it.
Remember, the goal is to find $d$ which is the multiplicative inverse of $e$ mod $(p_1-1)(p_2-1)$, or in other words $de \equiv 1 \pmod{(p_1-1)(p_2-1)}$. You have shown $1 = 40 \cdot 1 -13e$. If you read this equation mod 40, it says $1 \equiv -13e \pmod{40}$. So $d=-13$ achieves what we want. Of course, if you want a "positive" answer, note that $-13 \equiv 27 \pmod{40}$.