Finding d in RSA.

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.

• $d$ needs to satisfy $de \equiv 1 \pmod{40}$. So you need $d=-13$ or equivalently $d=27$. – Nate Eldredge Apr 29 '14 at 0:11
• Nate, you have answered it; then why call it a comment; post it as an answer and settle this question. – P Vanchinathan Apr 29 '14 at 0:29
• Im still not following. Did you solve it by. d(3) ≡ 1(mod 40) ? – Armin Apr 29 '14 at 0:30

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}$.
• Just a short note: If the goal is to find a decrpytion exponent for $n=55, e=3$, then $d=27$ is not the solution, $d=7$ or $d=47$ or more generally $d = 7 + k\lambda(55) = 7 + 20k$ will work too. – gammatester Apr 29 '14 at 7:59