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