<s>[INST] Using euclidean algo to find d (RSA encryption) The questions says "let p = 5, q =11, n = 55 tocient(n) = 40. e=7.
Use the Euclidean algo to find the value of d.
This is driving me crazy. Here's what I did:
40=5(7) +5
7= 1(5) + 2
5= 2(2) +1
2 = 2(1) + 0

So the GCD is 1.
Now to get 1 = de +f*tocient(n) to find d.
1 = 5 - 2(2) => 1 = 5 - 2(7-5) => 1= -2(7) + 3(5) => 1 = -2(7) +3(40 - 5(7))
=> 1 = -17(7) +3(40)

Therefore d = -17. But how can that be when in order to decode a message I have to use c^d mod n.
I don't think d can be negative but I don't know what I'm doing wrong. Any help would be great!
Regards
OSFTW
 [/INST] Mathematically, it's fine for $d$ to be negative, but because positive powers don't require computing the inverse, you may wish to make it positive. To do so, add and subtract $7 \cdot 40$ from the rightmost side:
$$
\begin{align}
1 &= -17 \cdot 7 + 3 \cdot 40 \\
&= -17 \cdot 7 + \color{red}{40 \cdot 7} + 3 \cdot 40 - \color{red}{7 \cdot 40 }\\
1 &= \ \qquad 23 \cdot 7 \qquad+ \quad -4 \cdot 40
\end{align}
$$
</s>